UVA 3027 / Live Archive 3027：並查集維護距離

問題描述

有 n 個節點，初始各自獨立。操作：

• I u v：將 u 的父節點設為 v，u 到 v 的距離為 |u-v| % 1000。
• E u：查詢 u 到根節點的距離。
• O：結束當前測試用例。

解題思路

帶權並查集。維護 parent[x] 和 dist[x]（x 到父節點的距離）。find(x) 時路徑壓縮並累加距離：dist[x] += dist[parent[x]]; parent[x] = find(parent[x])。合併時直接設 parent[u] = v; dist[u] = |u-v|%1000。查詢先 find(u) 再輸出 dist[u]。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 20005;
int parent[MAXN], dist[MAXN];

int find(int x) {
    if (x != parent[x]) {
        int p = parent[x];
        parent[x] = find(p);
        dist[x] += dist[p];
    }
    return parent[x];
}

void unite(int u, int v) {
    parent[u] = v;
    dist[u] = abs(u - v) % 1000;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; ++i) { parent[i] = i; dist[i] = 0; }
        char op;
        while (cin >> op) {
            if (op == 'O') break;
            if (op == 'I') {
                int u, v; scanf("%d%d", &u, &v);
                unite(u, v);
            } else if (op == 'E') {
                int u; scanf("%d", &u);
                find(u);
                printf("%d\n", dist[u]);
            }
        }
    }
    return 0;
}

複雜度分析

• 時間複雜度：O((n+q) α(n))。
• 空間複雜度：O(n)。

總結

帶權並查集經典應用，路徑壓縮時同步更新距離。注意距離定義為到父節點的距離，查詢時需先 find 確保路徑壓縮完成。