[Jungol] 정올 1863 종교

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1136&sca=4050

Approach

Disjoint-Set & Union-Find  

Disjoint-Set & Union-Find

---

#include <stdio.h>
const int LM = 50005;
int N, M, group[LM], ans;
int find(int n) {
    if (group[n] == n) return n;
    group[n] = find(group[n]);
    return group[n];
}

int main() {
    // freopen("input.txt", "r", stdin);
    int u, v;
    scanf("%d %d", &N, &M);
    ans = N;
    for (int i = 1; i <= N; ++i)
        group[i] = i;

    for (int i = 0; i < M; ++i) {
        scanf("%d %d", &u, &v);
        u = find(u), v = find(v);
        if (u == v) continue;
        ans--;
        group[v] = u;
    }

    printf("%d\n", ans);
}