ZOJ 3811 Untrusted Patrol 另解：純 DFS 遞歸標記

解法對比

本解法採用 遞歸 DFS 而非並查集，邏輯更直觀：

1. 按信號順序依次從觸發器節點 DFS，只走「未訪問」且「無觸發器/已處理觸發器」的節點
2. 遇到下一信號對應的觸發器節點即停止當前 DFS，標記可達
3. 若某信號節點不可達 → No
4. 最後再做一次全圖 DFS 檢查連通性

代碼實現

#include <iostream>
#include <cstring>
#include <vector>

const int MAXN = 110000;
int head[MAXN], vis[MAXN], sensor[MAXN];
struct Edge { int to, next; } edges[MAXN*4];
int ecnt;

void addEdge(int u, int v) {
    edges[ecnt] = {v, head[u]}; head[u] = ecnt++;
    edges[ecnt] = {u, head[v]}; head[v] = ecnt++;
}

void dfs(int u) {
    vis[u] = 1;
    for (int e = head[u]; ~e; e = edges[e].next) {
        int v = edges[e].to;
        if (vis[v]) continue;
        if (sensor[v]) { vis[v] = 1; continue; }  // 遇到未激活觸發器停止
        dfs(v);
    }
}

void dfsAll(int u, int& cnt) {
    vis[u] = 1; ++cnt;
    for (int e = head[u]; ~e; e = edges[e].next) {
        int v = edges[e].to;
        if (!vis[v]) dfsAll(v, cnt);
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(head, -1, sizeof head);
        memset(vis, 0, sizeof vis);
        memset(sensor, 0, sizeof sensor);
        ecnt = 0;

        int n, m, k; scanf("%d%d%d", &n, &m, &k);
        for (int i=0, x; i