Cod sursa(job #202185)
Utilizator | Data | 6 august 2008 17:53:52 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 15 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
#include<stdio.h>
FILE *f,*g;
long n,m,nr,i,x,y,a[100001];
int main()
{ f=fopen("dfs.in","r"); g=fopen("dfs.out","w");
fscanf(f,"%ld%ld",&n,&m);
nr=0;
for(i=1;i<=m;i++)
{ fscanf(f,"%ld%ld",&x,&y);
if(i==1) { a[x]=1; a[y]=1; nr=1; }
else
{ if(a[x]&&!a[y]) a[y]=a[x];
else if(a[y]&&!a[x]) a[x]=a[y];
else if(!a[x]&&!a[y]) { nr++; a[x]=a[y]=nr; }
}
}
for(i=1;i<=n;i++) if(a[i]==0) nr++;
fprintf(g,"%ld",nr);
fclose(g);
return 0;
}