Cod sursa(job #765381)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 7 iulie 2012 13:35:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include<cstdio>
#define N 100001
int a[3*N],b[3*N],*g[N],w[N],n,m,i,t,c[N];

void D(int i)
{int j;
c[i]=1;
for(j=0;j<w[i];j++)
if(!c[g[i][j]])
      D(g[i][j]);}

int main()
{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[i],&b[i]),w[a[i]]++,w[b[i]]++;
for(i=1;i<=n;w[i++]=0)
      g[i]=new int[w[i]];
for(i=1;i<=m;i++)
      g[a[i]][w[a[i]]++]=b[i],g[b[i]][w[b[i]]++]=a[i];
for(i=1;i<=n;i++)
if(!c[i])
      D(i),t++;
printf("%d",t);
return 0;}