记录编号	115110	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000]病毒	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2014-08-14 11:26:50	内存使用	0.83 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int SIZEN=30010;
bool bad[SIZEN]={0};//是病毒则为1
int child[SIZEN][2]={0};//这是Trie图,如果Trie中没有孩子就沿着fail找
int fail[SIZEN]={0};
int tot=0;
//root=0
int N;
char str[SIZEN]={0};
queue<int> Q;
int step(int x,int k){
	while(true){
		if(child[x][k]!=-1) return child[x][k];
		if(!x) return 0;
		x=fail[x];
	}
}
void make_Trie_graph(void){
	fail[0]=0;
	Q.push(0);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<=1;i++){
			if(child[x][i]!=-1){
				if(!x) fail[child[x][i]]=0;//这不需要考虑bad的问题
				else{
					fail[child[x][i]]=step(fail[x],i);
					bad[child[x][i]]|=bad[fail[child[x][i]]];
				}
				Q.push(child[x][i]);
			}
			else child[x][i]=step(x,i);//为了能够转移将其补齐
		}
	}
}
int vis[SIZEN]={0};
bool findcir(int x){
	vis[x]=-1;
	for(int i=0;i<=1;i++){
		if(bad[child[x][i]]) continue;
		if(vis[child[x][i]]==-1) return true;
		else if(vis[child[x][i]]==0){
			if(findcir(child[x][i])) return true;
		}
	}
	vis[x]=1;
	return false;
}
void init(void){
	memset(child,-1,sizeof(child));
	memset(fail,-1,sizeof(fail));
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%s",str);
		int x=0;
		for(int i=0;str[i];i++){
			int k=str[i]-'0';
			if(child[x][k]==-1) child[x][k]=++tot;
			x=child[x][k];
		}
		bad[x]=true;
	}
}
int main(){
	freopen("wir.in","r",stdin);
	freopen("wir.out","w",stdout);
	init();
	make_Trie_graph();
	if(findcir(0)) printf("TAK\n");
	else printf("NIE\n");
	return 0;
}