Cod sursa(job #293614)

Utilizator petrecgClinciu Glisca Petre petrecg Data 1 aprilie 2009 22:35:55
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 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)
{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;}
   if(fin[y]==0){st[y]=fin[y]=l+1;l++;a[1][l]=x;}
	  else{a[2][fin[y]]=l+1;fin[y]=l+1;l++;a[1][l]=x;}

  }
 for(i=1;i<=n;i++)if(v[i]==0){k++;dfs(i);}
 printf("%ld",k);
 fclose(stdin);fclose(stdout);
 return 0;
}