Cod sursa(job #603854)

Utilizator soriynSorin Rita soriyn Data 18 iulie 2011 20:48:04
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<stdio.h>
#include<vector>

#define maxn 100005

using namespace std;

vector <int> vecini[maxn];
int n,m,viz[maxn],size;

void citire()
{
	freopen("dfs.in","r",stdin);
	scanf("%d %d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++)
	{ 
		scanf("%d %d",&x,&y);
		vecini[x].push_back(y);
	}
}

void dfs(int nod)
{
	int p;
	viz[nod]=1;
	
	for(int i=0;i<vecini[nod].size();i++)
	   {
		   p=vecini[nod][i];
		   if(viz[p]==0)
		   dfs(p);
	}
}

int main()
{
	freopen("dfs.out","w",stdout);
	citire();
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(viz[i]==0) cnt++,dfs(i);
	printf("%d",cnt);
}