Pagini recente » Cod sursa (job #2872100) | Cod sursa (job #2170186) | Cod sursa (job #1096382) | Cod sursa (job #1445197) | Cod sursa (job #540423)
Cod sursa(job #540423)
#include <stdio.h>
long a[100000][100000],c[100000],viz[100000];
long i,k,n,m,x,y;
void citire ()
{
long i;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%ld %ld", &n, &m);
for(i=1;i<=m;i++)
{
scanf("%ld %ld", &x, &y);
a[x][y]=a[y][x]=1;
}
}
void bf (long a[100000][100000], long n, long x)
{
long p,u,v;
c[1]=x; viz[x]=1;
p=u=1;
while(p<=u)
{
v=c[p++];
for(i=1;i<=n;i++)
if(a[v][i]==1 && viz[i]==0)
{
c[++u]=i;
viz[i]=1;
}
}
}
void comp_conexe ()
{
long i;
for(i=1;i<=n;++i) viz[i]=0;
x=1;
do
{
k++;
bf(a,n,x);
x=1;
while(viz[x]==1 && x<=n) x++;
}while(x<=n);
}
int main ()
{
citire ();
comp_conexe ();
printf("%ld", k);
return 0;
}