BZOJ 2938 [POI2000] 病毒：AC自動機 + 拓撲排序判斷無限安全串

題目大意

給定 n 個病毒代碼片段（01串，總長 ≤ 30000）。若一個二進制串不包含任一病毒片段作為子串，則稱其為「安全的」。問：是否存在無限長的安全串？存在輸出 TAK，否則 NIE。

核心建模：AC自動機構建有向圖

1. 將所有病毒片段插入 Trie，標記結尾節點為「危險」
2. 構建失配指針，形成 AC 自動機（確定性有限自動機 DFA）
3. 傳遞危險標記：danger[u] |= danger[fail[u]]（若失配祖先是危險的，則當前節點也危險）
4. 自動機中非危險節點及其轉移邊構成一個有向圖

關鍵定理

存在無限長安全串 ⇔ 非危險節點構成的有向圖中存在環。

證明：

• → 若有無限安全串，對應自動機上一條無限路徑，節點有限必經歷環
• ← 若非危險子圖有環，可無限繞行環產生任意長安全串

算法：拓撲排序檢測環

1. 統計非危險節點的入度（僅考慮指向非危險節點的邊）
2. 將入度為 0 的非危險節點入隊
3. 拓撲排序：彈出節點，減少其出邊目標入度，入度歸 0 入隊
4. 若最終處理的非危險節點數 < 總非危險節點數，說明有環 → TAK；否則 NIE

關鍵代碼

// AC自動機構建（同標準 BFS）
void build_ac() {
    queue q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        danger[u] |= danger[fail[u]]; // 傳遞危險標記
        for (int c = 0; c < 2; ++c) {
            if (trie[u][c]) {
                fail[trie[u][c]] = trie[fail[u]][c];
                q.push(trie[u][c]);
            } else {
                trie[u][c] = trie[fail[u]][c];
            }
        }
    }
}

// 拓撲排序檢測環
bool has_infinite_safe() {
    vector in(tot + 1, 0);
    // 建圖並統計入度（僅非危險節點）
    for (int u = 1; u <= tot; ++u) {
        if (danger[u]) continue;
        for (int c = 0; c < 2; ++c) {
            int v = trie[u][c];
            if (!danger[v]) {
                in[v]++;
            }
        }
    }
    // 拓撲排序
    queue q;
    int cnt = 0;
    for (int u = 1; u <= tot; ++u) {
        if (!danger[u] && in[u] == 0) q.push(u);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cnt++;
        for (int c = 0; c < 2; ++c) {
            int v = trie[u][c];
            if (!danger[v] && --in[v] == 0) q.push(v);
        }
    }
    // 統計非危險節點總數
    int safe_total = 0;
    for (int u = 1; u <= tot; ++u) if (!danger[u]) safe_total++;
    return cnt < safe_total; // 有環
}

複雜度

• 構建 AC：O(總長度 × 字符集) = O(30000 × 2)
• 拓撲排序：O(節點數 + 邊數) = O(總長度)
• 總體：線性時間，極快

易錯點

1. 根節點危險性：若某病毒片段為空串（題目說非空），根不危險
2. 失配傳遞危險：danger[u] |= danger[fail[u]] 必須在 BFS 中按層序執行，保證祖先先處理
3. 補全轉移邊：trie[u][c] = trie[fail[u]][c] 確保圖完整
4. 輸出含義：有環 → 存在無限安全串 → TAK（波蘭語「是」），無環 → NIE（波蘭語「否」）