【題解】ZeroJudge d813: 10583 – Ubiquitous Religions

#include <iostream>
using namespace std;
const int maxn = 50000+5;
int pa[maxn];

int Find(int x){
    return pa[x] == x ? x : pa[x] = Find(pa[x]);
}

bool Union(int x, int y){
    int g1 = Find(x);
    int g2 = Find(y);
    if (g1 == g2) return false;
    else{
        pa[g2] = g1;
        return true;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, x, y, Case = 1;
    while (cin >> n >> m && n+m){
        for (int i = 0; i < maxn; i++){
            pa[i] = i;
        }
        int ans = n;
        while (m--){
            cin >> x >> y;
            if (Union(x, y)) {
                ans--;
            }
        }
        cout << "Case " << Case++ << ": ";
        cout << ans << "\n";
    }
    return 0;
}

import sys

def Find(x):
    if (pa[x] == x):
        return x
    else:
        pa[x] = Find(pa[x])
        return pa[x]
    
def Union(x, y):
    g1 = Find(x)
    g2 = Find(y)
    if (g1 == g2):
        return False
    else:
        pa[g2] = g1
        return True
    
lines = sys.stdin.readlines()
idx = -1
Case = 0
while True:
    try:
        idx += 1
        n, m = map(int, lines[idx].split())
        if n == 0 and m == 0:
            break
        Case += 1
        pa = []
        for i in range(n+1):
            pa.append(i)
            
        ans = n
        for i in range(m):
            idx += 1
            x, y = map(int, lines[idx].split())
            if (Union(x, y)):
                ans -= 1
        print(f"Case {Case}: {ans}")
    except:
        break