Pagini recente » Cod sursa (job #1131715) | Cod sursa (job #482772) | Cod sursa (job #1769187) | Cod sursa (job #592947) | Cod sursa (job #715043)
Cod sursa(job #715043)
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
struct Conn {
int node;
Conn * next;
};
int n, m;
bool vis[100001];
Conn * ind[100001];
void add(int a, int b) {
Conn * conn = new Conn();
conn->node = b;
conn->next = ind[a];
ind[a] = conn;
}
void visit(int id) {
vis[id] = 1;
Conn * next = ind[id];
while (next) {
if (!vis[next->node]) {
visit(next->node);
}
next = next->next;
}
}
int main() {
FILE * in = fopen("dfs.in", "rt");
FILE * out = fopen("dfs.out", "wt");
fscanf(in, "%d%d", &n, &m);
int a, b;
for (int i = 0; i < m; ++i) {
fscanf(in, "%d%d", &a, &b);
add(a, b);
add(b, a);
}
int count = 0;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
visit(i);
++count;
}
}
fprintf(out, "%d\n", count);
fclose(in);
fclose(out);
}