Cod sursa(job #392498)

Utilizator SheepBOYFelix Liviu SheepBOY Data 7 februarie 2010 16:37:00
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
int deg[100001],*vec[100001];
bool cnx[100001];
int NDFS(int nd)
{
	deg[nd]=1;
	if(!cnx[nd])
		return 1;
	else
	{
		int sum=0;
		for(int j=1;j<vec[nd][0];++j)
			if(!deg[vec[nd][j]])
			{
				deg[vec[nd][j]]=1;
				sum+=NDFS(vec[nd][j]);
			}
	return sum+1;
	}
}
int main()
{
	int aux1,aux2,n,m,i,fn=0;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i)
	{
		scanf("%d%d",&aux1,&aux2);
		if(aux1!=aux2)
		{
			cnx[aux1]=1;
			deg[aux1]++;
		}
		if(!fn)
			fn=aux1;
	}
	freopen("dfs.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i)
	{
		scanf("%d%d",&aux1,&aux2);
		if(deg[aux1])
		{
			vec[aux1]=new int[deg[aux1]+1];
			vec[aux1][0]=1;
			vec[aux1][vec[aux1][0]++]=aux2;
			deg[aux1]=0;
		}
		else
			if(aux1!=aux2)
				vec[aux1][vec[aux1][0]++]=aux2;
	}
	printf("%d",NDFS(fn));
return 0;
}