Cod sursa(job #755350)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 5 iunie 2012 15:04:30
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include<cstdio>
#include<vector>

using namespace std;

vector<int> L[100001];
int n,m,i,viz[100001],x,y,nr;

void dfs(int x)
{
	int i;
	viz[x]=1;
	for (i=0;i<=L[x].size()-1;i++)
	{
		if (viz[L[x][i]]==0)
		{
			viz[L[x][i]]=1;
			dfs(L[x][i]);
		}
	}
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		L[x].push_back(y);
	}
	nr=0;
	for (i=1;i<=n;i++)
	{
		if (viz[i]==0)
		{
			nr++;
			dfs(i);
		}
	}
	printf("%d\n",nr);
}