记录编号	157189	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[POI 2000]病毒	最终得分	100
用户昵称	清羽	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2015-04-08 06:38:27	内存使用	0.92 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int maxnode=30050;
const int sigma_size=2;

bool val[maxnode],have_cycle;
int n,sz,vis[maxnode],ch[maxnode][sigma_size],f[maxnode],last[maxnode];

int idx(int x)
{
	return x-'0';
}

void insert(char* s)
{
	int u=0,n=strlen(s);
	for(int i=0;i<n;i++){
		int v=idx(s[i]);
		if(!ch[u][v]) ch[u][v]=++sz;
		u=ch[u][v];
	}
	val[u]=true;
}

void GetFail()
{
	queue<int> q;
	for(int i=0;i<sigma_size;i++){
		int u=ch[0][i];
		if(u){
			q.push(u);last[u]=0;f[u]=0;
		}
	}
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=0;i<sigma_size;i++){
			int v=ch[u][i],j=f[u];
			if(!v){
				ch[u][i]=ch[f[u]][i];
				continue;
			}
			q.push(v);
			while(j && !ch[j][i]) j=f[j];
			f[v]=ch[j][i];
			last[v]=val[f[v]]?f[v]:last[f[v]];
		}
	}
}

bool dfs(int u)
{
 	vis[u]=-1;
 	for(int i=0;i<sigma_size;i++){
 		int v=ch[u][i];
 		if(last[v] || val[v] || vis[v]==1) continue;
 		if(vis[v]==-1) return true;	
 		if(dfs(v)) return true;
	}
	vis[u]=1;
	return false;
}

void init()
{
	memset(f,0,sizeof(f));
	memset(last,0,sizeof(last));
	memset(val,false,sizeof(val));
	sz=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		char s[30050];
		scanf("%s",s);
		insert(s);
	}
	GetFail();
}

void work()
{
	memset(vis,0,sizeof(vis));
	have_cycle=false;
	if(dfs(0)) printf("TAK");
	else printf("NIE");
}

int main()
{
	freopen("wir.in","r",stdin);
	freopen("wir.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}