P2444 [POI2000] 病毒

SunnyYuan的博客 / 2024-09-25 / 原文

题目

思路

使用 AC 自动机，将树建出，跑 getfail，然后在新图上找环，如果找到环，那么输出 TAK，否则 NIE。

如果一个点不能走（走到就匹配了），那么在 fail 树上，它的子孙结点也不能走，这个可以在 getfail 函数中预处理。

当然，写这篇博客的主要目的不是上述内容，而是普及组的找环！

找环不能只使用一个 vis 数组，进 dfs 标记然后在出的时候撤销标记，那样不是 $O(n)$ 的，还要加 st 数组，标记这个节点是否标记过，如果标记，那么就不用继续处理了。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct _ac {
    const int root = 0;
    int ch[N][2], idx = 0;
    int fail[N * 2];
    int g[N * 2];
    
    void insert(string& s) {
        int p = root;
        for (auto x : s) {
            int u = x - '0';
            if (!ch[p][u]) ch[p][u] = ++idx;
            p = ch[p][u];
        }
        g[p] = 1;
    }

    void getfail() {
        queue<int> q;

        for (int i = 0; i < 2; i++) {
            if (ch[0][i]) {
                q.push(ch[0][i]);
            }
        }

        while (q.size()) {
            int t = q.front();
            q.pop();

            for (int i = 0; i < 2; i++) {
                if (ch[t][i]) {
                    fail[ch[t][i]] = ch[fail[t]][i], q.push(ch[t][i]);
                    if (g[fail[ch[t][i]]]) g[ch[t][i]] = 1;
                }
                else ch[t][i] = ch[fail[t]][i];
            }
        }
    }
} ac;

bool vis[N], st[N];
bool flag = false;

void dfs2(int u) {
    vis[u] = 1;
    st[u] = 1;
    for (int i = 0; i < 2; i++) {
        int to = ac.ch[u][i];
        if (ac.g[to]) continue;
        if (vis[to]) {
            cout << "TAK\n";
            exit(0);
        }
        if (st[to]) continue;
        dfs2(to);
    }
    vis[u] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    string s;
    while (t--) {
        cin >> s;
        ac.insert(s);
    }
    ac.getfail();
    dfs2(0);
    cout << "NIE\n";
    return 0;
}