【ディクショナリツリー+並列調査セット】poj 2513 Colored Sticks

Colored Sticks
http://poj.org/problem?id=2513
Description
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
Input
Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.
Output
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

标题:たくさんの木の棒があって、木の棒の両端はそれぞれ絵の具を塗って、もしポートの色が同じならば、この2つのポートはいっしょに結合することができて、与えた木の棒は1本の線につながることができますかを聞きます.
问题解:この问题を见ると、図を连想しやすく、各辺を通って一度だけ、オラパスがあります.オーラ経路があることは、図中のすべての点の度数が偶数であるか、2つの点の度数が奇数であるかを示している.
辞書ツリーで各色に番号を付け、これが連通図であるかどうかを調べて判断します.

#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
    int next[10];
    int id;
}head[100005];
bool flag;
int cnt;
char s[10005][15];
void build(char *t,int idx,int id)
{
    int len=strlen(t),k;
    for(int i=0;i<len;++i)
    {
        k=t[i]-'0';
        if(head[idx].next[k]==0)
           head[idx].next[k]=(cnt++);
        if((head[idx].id)&&(head[idx].id!=id))
            flag=false;
        idx=head[idx].next[k];
    }
    head[idx].id=id;
}
int main()
{
    int cas,n;
    scanf("%d",&cas);
    for(;cas--;)
    {
        flag=true;
        cnt=1;
        scanf("%d",&n);
        memset(head,0,sizeof(head));
        for(int i=1;i<=n;++i)
        {
            scanf("%s",s[i]);
            build(s[i],0,i);
        }
        if(flag==false)
        {
            puts("NO");
            continue;
        }
        for(int i=1;i<=n;++i)
        {
            build(s[i],0,i);
            if(flag==false) break;
        }
        if(flag) puts("YES");
        else     puts("NO");
    }
    return 0;
}