Pagini recente » Cod sursa (job #355954) | Cod sursa (job #977626) | Cod sursa (job #756143) | Cod sursa (job #3244513) | Cod sursa (job #296288)
Cod sursa(job #296288)
#include<stdio.h>
#include<stdlib.h>
#define dim 200002
int *a[dim];
int viz[dim];
int N, M, comp;
void dfs(int k)
{
int i;
viz[k] = 1;
for(i = 1; i <= a[k][0]; i++)
if(! viz[a[k][i]] )
dfs(a[k][i]);
}
int main()
{
int i, x, y;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &N, &M);
for(i = 1; i <= N; i++)
{
a[i] = (int *)realloc(a[i], sizeof(int));
a[i][0] = 0;
}
int xx;
while( M )
{
scanf("%d %d", &x, &y);
xx=x;
a[x][0]++;
a[x] = (int *)realloc(a[x], ( a[x][0] + 1 ) * sizeof(int));
a[x][a[x][0]] = y;
a[y][0]++;
a[y] = (int *)realloc(a[y], ( a[y][0] + 1 ) * sizeof(int));
a[y][a[y][0]] = xx;
M--;
}
for(i = 1; i <= N; i++)
if(! viz[i])
{
comp++;
dfs(i);
}
printf("%d \n", comp);
return 0;
}