Pagini recente » Cod sursa (job #1366616) | Cod sursa (job #3128063) | Cod sursa (job #2472281) | Cod sursa (job #1504094) | Cod sursa (job #184253)
Cod sursa(job #184253)
#include<stdio.h>
const int M=200010;
const int N=100010;
struct muchie{
int x,y;
};
muchie e[M];
int *a[N], v[N], n, m;
bool viz[N];
void citire(){
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&e[i].x,&e[i].y);
++v[e[i].x];
++v[e[i].y];
}
for(int i=1;i<=n;++i){
a[i]=new int[v[i]+1];
a[i][0]=0;
}
for(int i=1;i<=m;++i){
x=e[i].x;
y=e[i].y;
a[ x ][ ++a[x][0] ] = y;
a[ y ][ ++a[y][0] ] = x;
}
}
void df(int x){
viz[x]=true;
for(int i=1;i<=a[x][0];++i)
if(!viz[a[x][i]])
df(a[x][i]);
}
int nrcomp(){
int i,nr=0;
for(i=1;i<=n;++i)
if(!viz[i]){
df(i);
++nr;
}
return nr;
}
int main(){
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
citire();
printf("%d\n",nrcomp());
return 0;
}