Cod sursa(job #178265)

Utilizator mariussMarius Telespan mariuss Data 14 aprilie 2008 12:23:11
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<stdio.h>
#define nmax 100005
#define mmax 50
int tata[nmax][mmax];
int v[nmax];
int count=0;
int n;

void dfs(int pas)
{
    int i,j;
    
    if(tata[pas][0]!=-1)
	{

		for(i=1;i<=tata[pas][0];i++)
			dfs(tata[pas][i]);

	   tata[pas][0]=-1;
       return;

	}
}
int main()
{
	int i,j,m,a,b;

	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	scanf("%d %d",&n,&m);

	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&a,&b);
		tata[a][0]++;
		tata[a][ tata[a][0] ]=b;
	}


	for(j=1;j<=n;j++)
	{
		if(tata[j][0]!=-1)
		{
			count++;
			dfs(j);
		}

	}

	printf("%d",count);

	return 0;
}