ZOJ 3811 Untrusted Patrol：BFS 與並查集解法詳解

ZOJ 3811 Untrusted Patrol：BFS 與並查集解法詳解

題目連結：ZOJ 3811

題目大意

一個工廠有 N 個點（飲料堆），M 條雙向通道連接它們。有 K 個點安裝了感測器，保安巡邏時首次到達感測器會觸發記錄。給定 L 個按時間順序記錄的感測器位置，判斷保安是否可能走遍了所有點。保安可以從任意點開始，甚至可能「穿牆」、「傳送」等作弊行為。

輸入格式

多組測試資料。每組第一行為 T。每組包含：N、M、K；接著 K 個感測器位置；M 條邊；最後 L 及 L 個按時間排序的感測器記錄。

輸出格式

若保安可能正常巡邏並走遍所有點輸出 "Yes"，否則 "No"。

核心思路

1. 將無感測器的點視為自由通行區域，用並查集維護連通塊。
2. 按感測器觸發順序處理：每觸發一個感測器，將其相鄰的非感測器點加入圖中，並用 BFS 擴展連通塊。
3. 檢查相鄰兩個觸發記錄所在的連通塊是否相同，若不同說明保安作弊（如傳送）。
4. 最後驗證所有點是否都被訪問過。

關鍵代碼片段

bool solve() {
    if (k == 0) return true;
    if (l < k) return false;
    for (int i = 0; i < G.size(); i++) {
        int u = G[i];
        add(u);          // 將感測器 u 相鄰的非感測器點連入圖
        bfs(u);          // 從 u 擴展連通塊
        if (i >= 1) {
            int a = G[i-1], b = G[i];
            if (findroot(a) != findroot(b)) return false; // 連通塊不通 → 作弊
        }
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) return false; // 有點未走到
    return true;
}

複雜度分析

時間複雜度 O((N+M) α(N))，空間複雜度 O(N+M)，滿足限制（N≤100000, M≤200000）。

範例解析

Sample Input 中第一組感測器記錄為 4,2,1，連通性檢查失敗輸出 "No"；第二組記錄為 4,1,2 通過檢查且全點覆蓋輸出 "Yes"。