Cod sursa(job #701818)

Utilizator pandreeaePopescu Andreea pandreeae Data 1 martie 2012 17:59:13
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.44 kb
#include <cstdio>
using namespace std;
int a[200000][200000]={0}, n, m, e[100000]={0};

void df (int x)
{
	int i;
	e[x]=1;
	for(i=1;i<=n;i++)
		if(a[x][i]==1)
			df(i);
}

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