Cod sursa(job #293565)

Utilizator petrecgClinciu Glisca Petre petrecg Data 1 aprilie 2009 22:02:51
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <stdio.h>
long a[3][2000],v[1000],st[1000],fin[1000],i,x,y,n,m,k,l;
void dfs(long x)
{int i;
 v[x]=1;
 for(i=st[x];i;i=a[2][i])
  if(v[a[1][i]]==0)dfs(a[1][i]);

}
int main()
{freopen("dfs.in","r",stdin);freopen("dfs.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 for(i=1;i<=m;i++)
  {scanf("%ld%ld",&x,&y);
   if(fin[x]==0){st[x]=fin[x]=l+1;l++;a[1][l]=y;}
	  else{a[2][fin[x]]=l+1;fin[x]=l+1;l++;a[1][l]=y;}
  }
 for(i=1;i<=n;i++)if(v[i]==0){k++;dfs(i);}
 printf("%ld",k);
 fclose(stdin);fclose(stdout);
 return 0;
}