Immediate Decodability[UVA 644](Trie入門)

トランスファゲート
題意:ある数字列を与えて、ある数字列が別の列の接頭辞であるかどうかを判断する.
この問題は本当にTrieツリーのテンプレートの問題と言える.
まずTrieツリーを作成し、ツリーを作成するときにsumを記録して、1つのノードがどのくらいの列にこのノードが含まれているかを示し、endを記録して、このノードが1つの列の終わりであるかを示します.
その後dfs/bfsはTrieツリー全体を遍歴し,ノードxがend[x]=true&&sum[x]>=2を満たすと問題条件が成立する.

#include 
#include 
#include 
using namespace std;
string s;
int trie[1000][2];
int tot, sum[1000];
bool ennd[1000], ans;
void insert(string t) {
    int p = 1;
    for (int i = 0; i < (int)t.length(); i++) {
        int k = t[i] - '0';
        sum[p]++;
        if (!trie[p][k]) trie[p][k] = ++tot;
        p = trie[p][k];
    }
    sum[p]++;
    ennd[p] = 1;
}
void dfs(int x) {
    if (ennd[x] && sum[x] >= 2) ans = 1;
    if (trie[x][0]) {
        dfs(trie[x][0]);
    }
    if (trie[x][1]) {
        dfs(trie[x][1]);
    }
}
int case_num;
int main() {
    while (cin >> s) {
        case_num++;
        if (s[0] == '9') continue;
        ans = 0;
        tot = 1;
        memset(ennd, 0, sizeof(ennd));
        memset(sum, 0, sizeof(sum));
        memset(trie, 0, sizeof(trie));
        insert(s);
        while (cin >> s) {
            if (s[0] == '9') break;
            insert(s);
        }
        dfs(1);
        if (ans) printf("Set %d is not immediately decodable
", case_num);
        else printf("Set %d is immediately decodable
", case_num);
    }
    return 0;
}