Description

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。

任务：

请写一个程序：

l         读入病毒代码；

l         判断是否存在一个无限长的安全代码；

l         将结果输出

Input

 

第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。

Output

你应在在文本文件WIN.OUT的第一行输出一个单词：

l         TAK——假如存在这样的代码；

l         NIE——如果不存在。

Sample Input

3

01

11

00000

Sample Output

NIE

 

把trie树补成trie图，假如一个安全的串放在AC自动机上跑，一定不能碰到end节点，而且由于要一直跑下去，所以要形成一个环才可以。

所以这道题就是在trie图上找环。

这才发现trie图妙用无穷但是我一个也不会

代码

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define M 30001 6 using namespace std; 7 int n,cnt; 8 int fail[M]; 9 bool end[M],ins[M],vis[M];10 int ch[M][2];11 char s[M];12 void insert(string s)13 {14     int len=s.length();15     int now=0;16     for(int i=0;i
          

q;26 for(int i=0;i<2;i++)27 if(ch[0][i])28 q.push(ch[0][i]);29 while(!q.empty())30 {31 int u=q.front();32 q.pop();33 for(int i=0;i<2;i++)34 {35 if(ch[u][i])36 {37 end[ch[u][i]]|=end[ch[fail[u]][i]];38 fail[ch[u][i]]=ch[fail[u]][i];39 q.push(ch[u][i]);40 }41 else ch[u][i]=ch[fail[u]][i];42 }43 }44 }45 bool dfs(int x)46 {47 ins[x]=true;48 for(int i=0;i<2;i++)49 {50 int to=ch[x][i];51 if(ins[ch[x][i]]) return 1;52 if(vis[to]||end[to]) continue;53 vis[to]=true;54 if(dfs(to)) return 1;55 }56 ins[x]=0;57 return 0;58 }59 int main()60 {61 scanf("%d",&n);62 for(int i=1;i<=n;i++)63 {64 scanf("%s",s);65 insert(s);66 }67 build_fail();68 if(dfs(0)) printf("TAK");69 else printf("NIE");70 return 0;71 }