Pagini recente » Cod sursa (job #1398880) | Cod sursa (job #1614007) | Cod sursa (job #67300) | Cod sursa (job #481362) | Cod sursa (job #219295)
Cod sursa(job #219295)
#include <stdio.h>
const long N=100000;
long *a[N], x[N], y[N], d[N], viz[N];
void bfs(long x);
int main()
{
long i, conex=0, n, m;
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[i], &y[i]);
d[x[i]]++;
d[y[i]]++;
}//for i
for (i=1;i<=n; i++)
{
a[i]=new long[d[i]+1];
a[i][0]=0;
}//for i
for (i=1; i<=m; i++)
{
a[x[i]][++a[x[i]][0]]=y[i];
a[y[i]][++a[y[i]][0]]=x[i];
}//for i
for (i=1; i<=n; i++)
if (!viz[i])
{
conex++;
bfs(i);
}//if
printf("%ld", conex);
return 0;
}//main
void bfs(long x)
{
long coada[100000], p, u, i, y;
viz[x]=true;
coada[++u]=x;
p=u;
while (p<=u)
{
x=coada[p++];
for (i=1; i<=a[x][0]; i++)
{
y=a[x][i];
if (!viz[y])
{
viz[y]=true;
coada[++u]=y;
}//if
}//for i
}//while
}//bfs