POJ 2236 & 1611：並查集經典應用兩則

POJ 2236 Wireless Network：動態加點連通性查詢

題意

N (≤ 1000) 台電腦，坐標已知，通訊距離 ≤ d。初始均故障。操作：
`O x`：修復電腦 x。
`S x y`：查詢 x、y 是否連通（通過已修復電腦中繼）。

解法

• 預計算所有電腦對距離平方，判斷是否 ≤ d²。
• 並查集維護已修復電腦的連通分量。
• `O x`：標記 x 已修復，遍歷所有**已修復**電腦 y，若 `dist(x,y) ≤ d²` 則 `union(x,y)`。
• `S x y`：直接 `find(x)==find(y)` 判斷。

關鍵代碼

struct Point { int x, y; } p[1005];
bool repaired[1005];
int pre[1005], rnk[1005];

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) swap(x, y);
    pre[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
}

POJ 1611 The Suspects：傳染病擴散分組統計

題意

N (≤ 30000) 學生，M 組。0 號感染。同組傳染，組之間可交叉。求最終感染總人數。

解法

• 每組內所有學生 `union` 到第一個學生。
• 最後統計 `find(i) == find(0)` 的人數。

關鍵代碼

struct UF {
    int par[MAXN], rnk[MAXN];
    void init(int n) { for(int i=0;i<=n;++i){par[i]=i;rnk[i]=1;} }
    int find(int x) { return par[x]==x?x:par[x]=find(par[x]); }
    void unite(int x, int y) {
        x=find(x); y=find(y); if(x==y) return;
        if(rnk[x]