POJ 2236 Wireless Network：並查集動態連通性維護

題目大意

N (≤1001) 台電腦，坐標已知，通訊距離 ≤ d。操作兩類：

1. O p：修復電腦 p（激活）
2. S p q：查詢 p、q 能否通訊（直接或間接）

操作數 ≤ 300,000。輸出 "SUCCESS" 或 "FAIL"。

解法：並查集 + 激活時合併鄰居

• 預計算所有電腦對距離，構建鄰接表：adj[i] 存與 i 距離 ≤ d 的電腦
• 並查集維護已激活電腦的連通分量
• O p：激活 p，遍歷 adj[p]，若鄰居已激活，union(p, 鄰居)
• S p q：若 p、q 均激活且 find(p) == find(q) → SUCCESS

代碼實現

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

const int MAXN = 1005;

struct Computer {
    int x, y;
    bool active = false;
    vector adj;
} pc[MAXN];

int fa[MAXN];

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

void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) fa[fx] = fy;
}

double dist(int i, int j) {
    double dx = pc[i].x - pc[j].x;
    double dy = pc[i].y - pc[j].y;
    return sqrt(dx*dx + dy*dy);
}

int main() {
    int N; double d;
    scanf("%d %lf", &N, &d);
    for (int i = 1; i <= N; ++i) {
        scanf("%d %d", &pc[i].x, &pc[i].y);
        fa[i] = i;
    }
    // 預計算鄰接
    for (int i = 1; i <= N; ++i)
        for (int j = i+1; j <= N; ++j)
            if (dist(i, j) <= d + 1e-8) {  // 浮點誤差
                pc[i].adj.push_back(j);
                pc[j].adj.push_back(i);
            }
    
    char op;
    while (scanf(" %c", &op) == 1) {
        if (op == 'O') {
            int p; scanf("%d", &p);
            pc[p].active = true;
            for (int nb : pc[p].adj)
                if (pc[nb].active) unite(p, nb);
        } else if (op == 'S') {
            int p, q; scanf("%d %d", &p, &q);
            if (pc[p].active && pc[q].active && find(p) == find(q))
                puts("SUCCESS");
            else
                puts("FAIL");
        }
    }
    return 0;
}

關鍵優化

• 預計算鄰接表：O(N^2) 構建，查詢時只遍歷真鄰居，避免重複計算距離
• 路徑壓縮：find 遞歸壓縮，近乎 O(1)
• 浮點比較：加 1e-8 容差

複雜度

• 預處理：O(N^2) ≤ 10^6
• 每次 O：O(度數) ≤ O(N)
• 每次 S：O(α(N))
• 總時間：O(N^2 + Q α(N))，完全滿足限制

此題是並查集維護動態圖連通性的標準範例，「激活節點並合併已激活鄰居」模式廣泛應用於網絡恢復、社交網絡動態連通等場景。