学步园

Description

Binary Viruses Investigation
Committee detected, that certain sequences of zeroes and ones are codes
of viruses. The committee isolated a set of all the virus codes. A
sequence of zeroes and ones is called safe, if any of its segments (i.e.
sequence of consecutive elements) is not a virus code. The committee is
aiming at finding, whether an infinite, safe sequence of zeroes and
ones exists.
Example
For a set of codes {011, 11, 00000}, the sample infinite safe sequence
is 010101... . For a set of codes {01, 11, 00000} an infinite safe
sequence of zeroes and ones does not exist.

Task
Write a program, which:

reads virus codes from the text file WIR.IN,
determines, whether an infinite, safe sequence of zeroes and ones exists
writes the result to the text file WIR.OUT.

Input

The first line of the input
file WIR.IN consists of one integer n standing for the number of all
virus codes. Each of the next n lines consists of one non-empty word
composed from 0s and 1s - a virus code. The total length of all words
does not exceed 30000.

Output

In the first and the only line of the output file WIR.OUT one should find a word:

TAK - if an infinite, safe sequence of zeroes and ones exists.
NIE - otherwise.

Sample Input

Sample Output

Source

POI1999/2000

#include<iostream>
#include<cstring>
#include<stdio.h>

using namespace std;

struct Node {
    int next[2];
    int cnt;
    int suffix;
};

Node ptr[30003];
int que[30003];
char s[30003];
int tot, N;
int ind[30003], totnode;

void trie() {
    tot = 1;
    ptr[0].next[0] = ptr[0].next[1] = -1, ptr[0].cnt = 0;
    scanf("%d", &N);
    while (N--) {
        scanf("%s", s);
        int Len = strlen(s);
        int cur = 0;
        for (int i = 0; i < Len; i++) {
            if (ptr[cur].cnt) break;
            int k = s[i] - '0';
            if (ptr[cur].next[k] == -1) {
                ptr[cur].next[k] = tot;
                ptr[tot].next[0] = ptr[tot].next[1] = -1;
                ptr[tot].cnt = 0;
                tot++;
            }
            cur = ptr[cur].next[k];
        }
        ptr[cur].cnt = 1;
    }
//    cout << tot << endl;

}

void Bfs() {
    int l = 0, r = -1;
    totnode = 1;
    ptr[0].suffix = 0;
    for (int i = 0; i < tot; i++) {
        ind[i] = 0;
    }
    for (int i = 0; i < 2; i++) {
        if (ptr[0].next[i] == -1) {
            ptr[0].next[i] = 0, ind[0]++;
        } else {
            r++, que[r] = ptr[0].next[i], ptr[que[r]].suffix = 0, ind[que[r]]++;
        }
    }

    while (l <= r) {
        int cur = que[l];
        int suffix = ptr[cur].suffix;
        if (ptr[suffix].cnt) ptr[cur].cnt = 1;
        if (!ptr[cur].cnt) {
            totnode++;
            for (int i = 0; i < 2; i++) {
                if (ptr[cur].next[i] == -1) {
                    ptr[cur].next[i] = ptr[suffix].next[i];
                } else {
                    r++, que[r] = ptr[cur].next[i], ptr[que[r]].suffix = ptr[suffix].next[i];
                }
                ind[ptr[cur].next[i]]++;
            }

        }
        l++;
    }
//   for (int i = 0; i < tot; i++) cout << i << " " << ptr[i].next[0] << " " << ptr[i].next[1] << endl;
// for (int i = 0; i < tot; i++) cout << i << " " << ind[i] << endl;


}

void Topsort() {
    int l = 0, r = -1;
    if (ind[0] > 0) {
        printf("TAK\n");
        return;
    }
// cout << totnode << endl;

    r++, que[r] = 0;
    while (l <= r) {
        int cur = que[l];
        for (int i = 0; i < 2; i++) {
            int son = ptr[cur].next[i];
            if (ptr[son].cnt) continue;
            ind[son]--;
            if (ind[son] == 0) {
                r++, que[r] = son;
            }
        }
        l++;
    }
    if (r == totnode - 1) printf("NIE\n");
    else printf("TAK\n");
}

int main() {

    trie();
    Bfs();
    Topsort();
    return 0;
}

NIE

3
01 
11 
00000


[转]：http://hi.baidu.com/liveroom/blog/item/dcd20ff44f52f5d0f3d3850c.html