Pagini recente » Cod sursa (job #6317) | Cod sursa (job #508168) | Cod sursa (job #2100495) | Cod sursa (job #2044193) | Cod sursa (job #715041)
Cod sursa(job #715041)
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
struct Way {
int a, b;
};
bool cmp(Way a, Way b) {
return(a.a < b.a);
}
int n, m;
bool vis[100001];
int ind[100001];
Way way[200002];
void visit(int id) {
vis[id] = 1;
for (int i = ind[id]; way[i].a == id; ++i) {
if (!vis[way[i].b]) {
visit(way[i].b);
}
}
}
int main() {
FILE * in = fopen("dfs.in", "rt");
FILE * out = fopen("dfs.out", "wt");
fscanf(in, "%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
fscanf(in, "%d%d", &way[i].a, &way[i].b);
}
std::sort(way, way + m, cmp);
int k = 0;
for (int i = 0; i < m; ++i) {
if (k != way[i].a) {
k = way[i].a;
ind[k] = i;
}
}
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);
}