Pagini recente » Monitorul de evaluare | Organizatori, preONI 2006 | Rating Simion Alex (SimionAlex) | Rating Dogaru Mihail Danut (Matoka26) | Cod sursa (job #149048)
Cod sursa(job #149048)
#include<stdio.h>
int a[10000][10000],viz[10000];
long long n,m,nc;
void parc(int v)
{ int i,p,u,c[10000],vf;
p=u=1;
c[p]=v;
viz[v]=nc;
while(p<=u)
{ vf=c[p];
p++;
for(i=1;i<=n;i++)
if(a[vf][i] && !viz[i])
{ u++;
c[u]=i;
viz[i]=nc;
}
}
}
void conex()
{ int ok=1,i;
nc=1;
parc(1);
while(ok)
{ for(i=1;i<=n;i++)
if(viz[i]==0) break;
if(i<=n)
{ nc++;
parc(i);
}
else ok=0;
}
printf("%lld\n",nc);
}
int main()
{ freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%lld%lld",&n,&m);
int x,y,i;
for(i=1;i<=m;i++)
{ scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=1;
}
conex();
return 0;
}