病毒「POI 2000」

#include <bits/stdc++.h>
using namespace std;

int n, len;
char s[100005];

int ch[100005][2], fail[100005], tot;
bool tag[100005];

inline void insert(char *str, int l) {
	int x = 0;
	for (int i = 1; i <= l; i++) {
		if (!ch[x][str[i] - '0']) {
			ch[x][str[i] - '0'] = ++tot;
		}
		x = ch[x][str[i] - '0'];
	}
	tag[x] = 1;
}

queue<int> q;

inline void getfail() {
	for (int i = 0; i < 2; i++) if (ch[0][i]) q.push(ch[0][i]);
	while (!q.empty()) {
		int x = q.front(); q.pop();
		tag[x] |= tag[fail[x]];
		for (int i = 0; i < 2; i++) {
			if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
			else ch[x][i] = ch[fail[x]][i];
		}
	}
}

int dfn[30005], low[30005], stk[30005], tme, top;
bool vis[30005], flag;

void tarjan(int x) {
	dfn[x] = low[x] = ++tme; 
	vis[x] = 1; 
	stk[++top] = x; 
	for (int i = 0; i < 2; i++) {
		if (tag[ch[x][i]]) continue;
		int y = ch[x][i];
		if (x == y) flag = 1;
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		} else if (vis[y]) {
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (dfn[x] == low[x]) {
		int now = 0, totot = 0;
		do {
			now = stk[top--];
			vis[now] = 0;
			totot++;
		} while (now != x);
		if (totot > 1) flag = 1;
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		memset(s, 0, sizeof(s));
		scanf("%s", s+1); len = strlen(s+1);
		insert(s, len);
	}
	getfail();
	flag = 0;
	tarjan(0);
	if (flag) puts("TAK");
	else puts("NIE");
	return 0;
}