题意

\(n\)个01病毒串，总长不超过\(30000\)。问是否存在无限长的不包含病毒串的01串。

分析

考虑ac自动机，如果不包含病毒串而且无限长也就是说存在一个环（转移和fail树），使得环上不含病毒串。

题解

所以我们标记一下病毒串后dfs找环即可。

#include 
    
     using namespace std;const int N=30005;int ch[N][2], tot, go[N], vis[N], ins[N], q[N], f[N];bool dfs(int x) {    ins[x]=1;    vis[x]=1;    for(int i=0; i<2; ++i) {        int y=ch[x][i];        if(ins[y]) {            return 1;        }        if(go[y] || vis[y]) {            continue;        }        if(dfs(y)) {            return 1;        }    }    ins[x]=0;    return 0;}int main() {    int n;    scanf("%d", &n);    for(int i=0; i