病毒

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1993 字
AC 自动机去危险点后 DFS 找环
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1484
// 题意：给 n 个 01 病毒代码段，判断是否存在一个无限长的 01 串使得其中不含任何病毒代码段；存在输出 TAK，否则输出 NIE。
// 思路：病毒串建 AC 自动机并标出所有危险状态（自身结尾或 fail 链上有结尾），然后在自动机图上从根出发做 DFS 找环，能找到一个不经过危险状态的环就说明可以无限循环下去。
// 复杂度：O(病毒串总长 × 2) 时间 / O(病毒串总长) 空间
// 易错点：危险标记要沿 fail 链传递，只标自己的结尾会漏掉「后缀是病毒串」的状态。
// 易错点：找环必须用三色 DFS 判回边，只做一次可达性搜索会把「无环但可走有限步」的情况误判成存在。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[2];
    int fail;
    bool bad;
    Node(){
        ch[0] = ch[1] = 0;
        fail = 0;
        bad = false;
    }
};
vector<Node> tr;
vector<char> color;
bool dfs(int u){
    color[u] = 1;
    for(int c = 0; c < 2; c++){
        int v = tr[u].ch[c];
        if(tr[v].bad) continue;
        if(color[v] == 1) return true;
        if(color[v] == 0){
            if(dfs(v)) return true;
        }
    }
    color[u] = 2;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    tr.reserve(30000 + 5);
    tr.push_back(Node());
    for(int i = 0; i < n; i++){
        string w;
        cin >> w;
        int u = 0;
        for(int j = 0; j < (int)w.size(); j++){
            int c = w[j] - '0';
            if(!tr[u].ch[c]){
                tr[u].ch[c] = (int)tr.size();
                tr.push_back(Node());
            }
            u = tr[u].ch[c];
        }
        tr[u].bad = true;
    }
    queue<int> q;
    for(int c = 0; c < 2; c++){
        if(tr[0].ch[c]) q.push(tr[0].ch[c]);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if(tr[tr[u].fail].bad) tr[u].bad = true;
        for(int c = 0; c < 2; c++){
            int v = tr[u].ch[c];
            if(v){
                tr[v].fail = tr[tr[u].fail].ch[c];
                q.push(v);
            }else{
                tr[u].ch[c] = tr[tr[u].fail].ch[c];
            }
        }
    }
    int sz = (int)tr.size();
    color.assign(sz, 0);
    bool ok = dfs(0);
    cout << (ok ? "TAK" : "NIE") << "\n";
    return 0;
}
病毒

正文

一本通·提高篇的其它内容
