UVA10583 Ubiquitous Religions

Graph, Union Find

출처: UVA UVA10583 Ubiquitous Religions


SOL)
유니온 파인드를 쓰면 간단하게 해결되는 문제
총 Component의 수를 출력해주면 된다.


[-] Collapse

#include<stdio.h>
#include<vector>
using namespace std;

struct Union_Find{
    vector<int> parent, rank;
    int component;
    Union_Find(int n) :parent(n + 1), rank(n + 1), component(n){
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }
    int find(int u){
        if (parent[u] == u) return u;
        return find(parent[u]);
    }
    bool merge(int u, int v){
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) rank[v]++;
        component--;
        return true;
    }
};
int n, m;
int main(){
    //freopen("input.txt", "r", stdin);
    int testCase = 1;
    while (1){
        scanf("%d%d", &n, &m);
        if (n == 0 && m == 0) break;
        Union_Find uf(n);
        for (int i = 0; i < m; i++){
            int u, v;
            scanf("%d%d", &u, &v);
            uf.merge(u, v);
        }
        printf("Case %d: %d\n", testCase++, uf.component);
    }
}