Pagini recente » Cod sursa (job #1504636) | Profil arlechin96 | Cod sursa (job #1488214) | Cod sursa (job #936273) | Cod sursa (job #2720429)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream o("dfs.out");
void dfs(vector<int> *graph, int source, int *visited)
{
vector<int> stack;
int nod;
visited[source] = 1;
stack.push_back(source);
while (!stack.empty())
{
nod = stack.back();
stack.pop_back();
for (vector<int>::iterator i = graph[nod].begin(); i != graph[nod].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = 1;
stack.push_back(*i);
}
}
}
}
int main()
{
int noduri, arce, a, b;
f >> noduri >> arce;
vector<int> graph[noduri + 1];
for (int i = 0; i < noduri; i++)
{
f >> a >> b;
graph[a].push_back(b);
}
int visited[noduri + 1];
memset(visited, 0, (noduri + 1) * sizeof(int));
int n = 0;
for (int i = 1; i <= noduri; i++)
{
if (!visited[i])
{
n++;
dfs(graph, i, visited);
}
}
o << n;
}