「Bzoj 2938」「Poi2000」病毒 (AC自动机Trie图 + DFS找环)

bzoj 2938
题意：见上。

将AC自动机的Fail指针都连上，那么就形成了一个Trie图。在Trie图上找到一个不含危险点的环即有解，否则无解。

找环即用Tarjan的思想，模拟一个栈

知识点：
1、Trie图的运用
2、DFS找环

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 30000 + 5;

    int n, ch[MAXN][2], f[MAXN], danger[MAXN], sz;
    int vis[MAXN], ex[MAXN];
    char s[30000 + 5];
    queue<int > q;

    void insert(char *s) {
        int len = strlen(s), now = 0;
        for (int i = 0; i < len; ++i) {
            int c = s[i] - '0';
            if (!ch[now][c]) ch[now][c] = ++sz;
            now = ch[now][c];
            if (i == len - 1) danger[now] = 1;
        }
    }
    void getFail() {
        f[0] = 0;
        for (int c = 0; c < 2; ++c) {
            int v = ch[0][c];
            if (v) q.push(v), f[v] = 0; 
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int c = 0; c < 2; ++c) {
                int v = ch[u][c];
                if (!v) {ch[u][c] = ch[f[u]][c]; continue ;}
                q.push(v);
                int j = f[u];
                while (j && !ch[j][c]) j = f[j];
                f[v] = ch[j][c];
                if (danger[f[v]]) danger[v] = 1;
            }
        }
    }
    void dfs(int u) {
        if (ex[u]) {printf("TAK\n"); exit(0);}
        if (danger[u]) return ;
        if (vis[u]) return ;
        vis[u] = ex[u] = 1;
        dfs(ch[u][0]);
        dfs(ch[u][1]);
        ex[u] = 0;
    }

    void clean() {
        ms(ch, 0), ms(f, 0), ms(danger, 0), sz = 0;
        ms(vis, 0), ms(ex, 0);
    }
    int solve() {

        clean(); 
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            scanf("%s", s);
            insert(s);
        }
        getFail();
        dfs(0);
        printf("NIE\n");

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
1
1

1
0

1
01

2
01
10

2
1
0

3
011
11 
00000

3
011
11 
0
*/