Cod sursa(job #293592)

Utilizator petrecgClinciu Glisca Petre petrecg Data 1 aprilie 2009 22:24:58
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <stdio.h>
long a[3][200000],v[100000],st[100000],fin[100000],i,x,y,n,m,k,l;
void dfs(long x)
{long i;
 v[x]=1;i=st[x];
 while(i!=0)
 {if(v[a[1][i]]==0)dfs(a[1][i]);
  i=a[2][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;
}