Cod sursa(job #1497116)

Utilizator LegionHagiu Stefan Legion Data 6 octombrie 2015 08:46:01
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> nod[100001];
int g[100001];
void rez(int x)
{
	g[x] = 1;
	int i;
	for (i = 0; i < nod[x].size(); i++)
	{
		if (g[nod[x][i]]==0)
		rez(nod[x][i]);
	}
}
int main()
{
	ifstream in("dfs.in");
	ofstream out("dfs.out");
	int i, n, m, x, y,t=0;
	in >> n;
	in >> m;
	for (i = 1; i <= m; i++)
	{
		in >> x;
		in >> y;
		nod[x].push_back(y);
	}
	for (i = 1; i <= n; i++)
	{
		if (g[i] == 0)
		{
			rez(i);
			t++;
		}
	}
	out << t;
}