Cod sursa(job #748922)

Utilizator zeeboBuzatu Vlad zeebo Data 15 mai 2012 10:06:38
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector <int> gr[100000];
vector <int> :: iterator it;

bool sel[100000];
void dfs (int x)
{
	vector <int> :: iterator it;
	sel[x]=true;
	for (it=gr[x].begin();it!=gr[x].end();it++)
		if (!sel[*it])
		{
			sel[*it]=true;
			dfs(*it);
		}
}
int main ()
{
   int n,m,i,x,y,nc;
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		gr[x].pb(y);
    }
nc=0;
for (i=1;i<=n;i++)
	if (!sel[i])
	{
		nc++;
		dfs(i);
	}
g<<nc;

return 0;
}