算法1

blablabla

时间复杂度

参考文献

C++ 代码

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

const int N = 30010;
int n;
int tr[N][2], st[N], idx;
int ne[N], q[N], hh, tt;
int din[N], dout[N];
char str[N];
int color[N];
bool vis[N];

void insert()
{
    int p = 0;
    for(int i = 0; str[i]; ++ i)
    {
        int x = str[i] - '0';
        if(!tr[p][x]) tr[p][x] = ++ idx;
        p = tr[p][x];
    }
    st[p] = true;
}

void build()
{
    hh = 0, tt = -1;
    for(int i = 0; i < 2; ++ i)
        if(tr[0][i])
            q[++ tt ] = tr[0][i];
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(int i = 0; i < 2; ++ i)
        {
            int p = tr[t][i];
            if(!p) tr[t][i] = tr[ne[t]][i];
            else 
            {
                ne[p] = tr[ne[t]][i];
                q[++ tt ] = p;
            }
        }
    }
}

void dfs1(int u, bool tag)
{
    if(tag) st[u] = true;
    for(int i = 0; i < 2; ++ i)
    {
        if(!tr[u][i]) continue;
        if(st[u]) dfs1(tr[u][i], true);
        else dfs1(tr[u][i], false);
    }
}

bool dfs2(int u)
{
    color[u] = 0;
    for(int i = 0; i < 2; ++ i)
    {
        int j = tr[u][i];
        if(st[j]) continue;
        if(color[j] == 0) return true;
        else if(color[j] == -1 && dfs2(j)) return true;
    }
    color[u] = 1;
    return false;
}

void dfs3(int u)
{
    vis[u] = true;
    bool tag = false;
    int p = u;
    while(p)
    {
        if(st[p]) tag = true;
        p = ne[p];
    }
    if(tag) st[u] = true;
    for(int i = 0; i < 2; ++ i)
    {
        int j = tr[u][i];
        if(vis[j]) continue;
        dfs3(j);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
    {
        scanf("%s", str);
        insert();
    }
    dfs1(0, 0);
    build();
    dfs3(0);
    memset(color, -1, sizeof color);
    if(dfs2(0)) printf("TAK");
    else printf("NIE");
    return 0;
}