Pagini recente » Cod sursa (job #2271262) | Cod sursa (job #2549583) | Cod sursa (job #2849899) | Cod sursa (job #995609) | Cod sursa (job #184738)
Cod sursa(job #184738)
#include <stdio.h>
const int N=100015;
const int M=2*N;
int *a[N],v[N];
bool viz[N];
int n,m;
struct muchie{int x,y;};
muchie e[M];
void scan()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out", "w",stdout);
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];
}
}
void make_mat()
{
for(int i=0;i<=n;
a[i]=new int[v[i]+1],
a[i][0]=0,++i);
for(int i=1;i<=m;++i)
{
int 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()
{
scan();
make_mat();
printf("%d\n",nrcomp() );
return 0;
}