Pagini recente » Cod sursa (job #477953) | Cod sursa (job #2227887)
#include <stdio.h>
#include <ctype.h>
int N, M;
int boss[100000 + 1];
int set[100000 / 32 + 1];
void init() {
int u;
for (u = 1; u <= 100000; u++) {
boss[u] = u;
}
}
int find(int u) {
int r = u, tmp;
while (r != boss[r]) {
r = boss[r];
}
while (u != boss[u]) {
tmp = boss[u];
boss[u] = r;
u = tmp;
}
return r;
}
void unify(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
boss[v] = u;
}
}
int getBit(int x) {
return (set[x >> 5] >> (x & 31)) & 1;
}
void setBit(int x) {
set[x >> 5] |= 1 << (x & 31);
}
int main(void) {
FILE *f = fopen("dfs.in", "r");
init();
scanf("%d %d", &N, &M);
for (; M; M--) {
int x, y;
scanf("%d %d", &x, &y);
unify(x, y);
}
fclose(f);
int u, v, count = 0;
for (u = 1; u <= N; u++) {
v = find(u);
if (!getBit(v)) {
setBit(v);
count++;
}
}
freopen("dfs.out", "w", stdout);
fprintf(stdout, "%d\n", count);
return 0;
}