FZU 2192 種類並查集：城市-服務-人三層關係建模

題目場景

有城市、服務、人三類實體，編碼分段：1..N 城市，N+1..2N 服務，2N+1..3N 人。給定若干關係（如「人屬於某服務」「服務屬於某城市」），查詢某人所屬城市（輸出城市編號，若無則 0）。

種類並查集設計

• 所有節點共用一個 fa[]，初始 fa[i]=i。
• 合併策略：永遠將**較大編號**的根掛到**較小編號**根下。因為城市編號最小（1..N），服務次之，人最大。最終 find(x) 必指向該連通塊中**最小編號**，即城市（若存在）。
• 查詢時：root = find(x)；若 root > N 則無城市，輸出 0；否則輸出 root。

關鍵細節

1. **不使用 rank/size 啟發式**，必須強制「大掛小」以保證根為城市。
2. 路徑壓縮照常使用，不影響根的最小性。
3. 輸入關係可能重複/多餘，並查集天然去重。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
int fa[MAXN];

int findRoot(int x) {
    return fa[x] == x ? x : fa[x] = findRoot(fa[x]);
}

void unite(int x, int y) {
    x = findRoot(x); y = findRoot(y);
    if (x == y) return;
    if (x > y) swap(x, y);   // 強制小編號當根
    fa[y] = x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, Q;
    while (cin >> N >> M >> Q) {
        for (int i = 1; i <= 3*N; ++i) fa[i] = i;

        for (int i = 0; i < M; ++i) {
            int u, v; cin >> u >> v;
            unite(u, v);
        }

        while (Q--) {
            int x; cin >> x;
            int r = findRoot(x);
            if (r > N) cout << 0 << "\n";
            else cout << r << "\n";
        }
    }
    return 0;
}

複雜度

• 時間：O((N+M+Q) α(N))，近似線性。
• 空間：O(N)。