Cod sursa(job #178255)

Utilizator mariussMarius Telespan mariuss Data 14 aprilie 2008 12:13:36
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<stdio.h>
#define nmax 1010
#define mmax 1010
int tata[nmax][mmax];
int v[nmax];
int count=1;
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;
	}

	dfs(1);

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

	}

	printf("%d",count);

	return 0;
}