Pagini recente » Cod sursa (job #1137371) | Cod sursa (job #3145151) | Cod sursa (job #814282) | Cod sursa (job #3268863) | Cod sursa (job #160194)
Cod sursa(job #160194)
#include <stdio.h>
#define N 100000
#define M 200000
int* la[N+1];
int nv[N+1];
struct muchie
{
int x,y;
};
muchie vm[M];
int n,m,viz[N+1];
void citeste()
{
freopen("dfs.in","r",stdin);
scanf("%d%d\n",&n,&m);
int i;
for(i=1;i<=m;++i)
{
scanf("%d%d\n",&vm[i].x,&vm[i].y);
nv[vm[i].x]++;
nv[vm[i].y]++;
}
for(i=1;i<=n;++i)
{
la[i]=new int[nv[i]+1];
la[i][0]=0;
}
for(i=1;i<=m;++i)
{
la[vm[i].x][++la[vm[i].x][0]]=vm[i].y;
la[vm[i].y][++la[vm[i].y][0]]=vm[i].x;
}
fclose(stdin);
}
void df(int x)
{
viz[x]=1;
for(int i=1;i<=la[x][0];++i) if(!viz[la[x][i]]) df(la[x][i]);
}
int main()
{
citeste();
int cnt=0;
for(int i=1;i<=n;++i)
{
if(!viz[i])
{
++cnt;
df(i);
}
}
freopen("dfs.out","w",stdout);
printf("%d",cnt);
fclose(stdout);
return 0;
}