Mai intai trebuie sa te autentifici.
Cod sursa(job #185787)
Utilizator | Data | 26 aprilie 2008 00:38:48 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | c | Status | done |
Runda | Arhiva educationala | Marime | 0.98 kb |
#include <stdio.h>
#include <stdlib.h>
#define N 100010
int *a[N],n,m;
int cati[N];
int vizitat[N];
void dfs(int x){
int i;
vizitat[x]=1;
for (i=1;i<=cati[x];++i)
if (!vizitat[a[x][i]])
dfs(a[x][i]);
}
int main(){
int x,y,i,r=0;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=m;++i){
scanf("%d%d",&x,&y);
++cati[x];
++cati[y];
}
fclose(stdin);
for (i=1;i<=n;++i){
a[i]=(int*)malloc(cati[i]*sizeof(int));
//a[i]=new int[cati[i]+1];
cati[i]=0;
}
freopen("dfs.in","r",stdin);
scanf("%d%d",&n,&m);
for (i=1;i<=m;++i){
scanf("%d%d",&x,&y);
++cati[x];
a[x][cati[x]]=y;
++cati[y];
a[y][cati[y]]=x;
}
for (i=1;i<=n;++i)
if (!vizitat[i]){
dfs(i);
++r;
}
printf("%d\n",r);
return 0;
}