Pagini recente » Cod sursa (job #2783127) | Cod sursa (job #42667) | Istoria paginii utilizator/uaic_popa_padurariu_pavaloi | Cod sursa (job #365585) | Cod sursa (job #148818)
Cod sursa(job #148818)
#include<stdio.h>
#define maxn 100010
int viz[maxn],*vec[maxn],nr[maxn],n,m,conex;
struct vecin{
int x,y;
};
vecin a[2*maxn];
void df(int i){
int j;
viz[i]=1;
for(j=1;j<=vec[i][0];++j){
if(!viz[vec[i][j]])
df(vec[i][j]);
}
}
void citire(){
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i){
scanf("%d%d",&a[i].x,&a[i].y);
++nr[a[i].x];
++nr[a[i].y];
}
for(i=1;i<=n;++i){
vec[i]=new int [nr[i]+1];
vec[i][0]=0;
}
for(i=1;i<=m;++i){
vec[a[i].x][++vec[a[i].x][0]]=a[i].y;
vec[a[i].y][++vec[a[i].y][0]]=a[i].x;
}
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int i;
citire();
conex=0;
for(i=1;i<=n;++i){
if(!viz[i]){
++conex;
df(i);
}
}
printf("%d\n",conex);
fclose(stdin);
fclose(stdout);
return 0;
}