Pagini recente » Cod sursa (job #2353014) | Cod sursa (job #800628) | Cod sursa (job #1664388) | Cod sursa (job #67946) | Cod sursa (job #1399874)
#include <stdio.h>
#define MAX_N 100000
#define MAX_M 200000
#define NIL -1
typedef struct {
int v, next;
} cell;
cell l[2 * MAX_M];
int adj[MAX_N];
bool d[MAX_N];
void addEdge(int u, int v, int pos) {
l[pos].v = v;
l[pos].next = adj[u];
adj[u] = pos;
}
void dfs(int u) {
d[u] = 1;
for (int pos = adj[u]; pos != NIL; pos = l[pos].next) {
int v = l[pos].v;
if (!d[v]) {
dfs(v);
}
}
}
int main (void) {
FILE *f;
int n, m;
int u, v;
int ans;
f = fopen("dfs.in", "r");
fscanf(f, "%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
adj[i] = NIL;
}
for (int i = 0; i < m; ++i) {
fscanf(f, "%d%d", &u, &v);
addEdge(u - 1, v - 1, 2 * i);
addEdge(v - 1, u - 1, 2 * i + 1);
}
fclose(f);
ans = 0;
for (int i = 0; i < n; ++i) {
if (!d[i]) {
++ans;
dfs(i);
}
}
f = fopen("dfs.out", "w");
fprintf(f, "%d\n", ans);
fclose(f);
return 0;
}