Pagini recente » Cod sursa (job #2375334) | Cod sursa (job #2631565) | Cod sursa (job #35436) | Cod sursa (job #1677180) | Cod sursa (job #803393)
Cod sursa(job #803393)
#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define M 100001
typedef struct Muchie {
int x;
int y;
};
struct Muchie vm[N];
int g[M];
int n, m;
int *a[M];
int c[M];
int viz[N];
FILE *in;
FILE *out;
void citire()
{
fscanf(in, "%d %d", &n, &m);
int i;
for (i = 0; i < m; i++) {
fscanf(in, "%d %d", &vm[i].x, &vm[i].y);
g[vm[i].x]++;
g[vm[i].y]++;
}
for (i = 1; i <= n; i++) {
a[i] = (int*)malloc(g[i]*sizeof(int));
}
for (i = 0; i < m; i++) {
a[vm[i].x][++c[vm[i].x]] = vm[i].y;
a[vm[i].y][++c[vm[i].y]] = vm[i].x;
}
}
void fill(int x)
{
viz[x] = 1;
int i, y;
for (i = 1; i <= g[x]; i++) {
y = a[x][i];
if (!viz[y]) {
fill(y);
}
}
}
int main()
{
in = fopen("dfs.in", "r");
out = fopen("dfs.out", "w");
citire();
int i;
int count = 0;
for (i = 1; i <= n; i++) {
if (!viz[i]) {
count ++;
fill(i);
}
}
fprintf(out, "%d\n", count);
return 0;
}