NIE

题目链接

http://acm.hnu.cn/online/?action=problem&type=show&id=10104

思路分析：

仔细分析就会发现，如果在ac自动机上存在一个环，且这个环上没有单词的末尾节点，那么就可以。

为什么连单词的末尾节点也不行。

因为ac自动机上的next指向了的是与它具有最长后缀等于前缀的，如果这个时候后缀指向了单词末尾节点的前面，也就意味着有一个前缀在这个末尾节点的前面，那么这个环总会出现一个单词节点。

所以在dfs的时候，要避开一切的单词末尾节点。

至于dfs的时候，我们要判断的也是一条连续的链上的环，所以在深搜的时候用1去标记，然后回溯的时候，标记成另外一个。

然后没有标记的为0.

这样就可以找到链上成环的节点了。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 105
#define maxn 30005
using namespace std;
typedef long long ll;
const int mod = 100000;

const char tab = '0';
const int max_next = 2;

int next[maxn][max_next],fail[maxn],num[maxn],siz;

int newnode()
{
  for(int i=0;i<max_next;i++)
    next[siz][i]=0;
  fail[siz]=num[siz]=0;
  return siz++;
}
void init()
{
  siz=0;
  newnode();
}
void Insert(char *s,int len)
{
  int p=0;
  for(int i=0;i<len;i++)
  {
    int &x=next[p][s[i]-tab];
    p=x?x:x=newnode();
  }
  num[p]++;
}

void acbuild()
{
  queue<int>Q;
  Q.push(0);
  while(!Q.empty())
  {
    int temp=Q.front();
    Q.pop();
    for(int i=0;i<max_next;i++)
    {
      int v=next[temp][i];
      if(v==0)next[temp][i]=next[fail[temp]][i];
      else Q.push(v);
      if(temp!=0)fail[v]=next[fail[temp]][i];
      if(num[next[fail[temp]][i]])num[next[temp][i]]++;
    }
  }
}
int vis[maxn];
bool dfs(int now)
{
  vis[now]=1;
  for(int j=0;j<max_next;j++)
  {
    if(num[next[now][j]])continue;
    if(vis[next[now][j]]==1)return true;
    if(vis[next[now][j]]==0 && dfs(next[now][j]))return true;
  }
  vis[now]=-1;
  return false;
}

char word[30005];
int main()
{
  int n,L;
  while(scanf("%d",&n)!=EOF)
  {
    init();
    for(int i=1;i<=n;i++)
    {
      scanf("%s",word);
      Insert(word,strlen(word));
    }
    acbuild();
    memset(vis,0,sizeof vis);
    bool ans=false;
    for(int i=0;i<siz;i++)
    if(!vis[i] && dfs(i))
    {
      ans=true;
      break;
    }
    acdebug();
    if(ans)puts("TAK\n");
    else puts("NIE\n");
  }
  return 0;
}