题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=230

题意：给你许许多多的木棍，没条木棍两端有两种颜色，问你在将木棍相连时，接触的端点颜色必须相同，是否能把它们都连起来

思路：很明显的欧拉路径，但题目给的字符串数据很大，得用字典树存取。

代码如下：

#include "stdio.h"

#include "string.h"

#include "stdlib.h"

#define N 505000

int set[N],du[N];

int find(int x)

{

    if(set[x]==-1) return x;

    return set[x]=find(set[x]);

}

void bing(int a,int b)

{

    int fa = find(a);

    int fb = find(b);

    if(fa!=fb) set[fa] = fb;

}

struct node

{

    struct node *next[26];

    int num;

};

int id;

void BFS(node *root);

int Trie(node *root,char *s);

void Date_process(int n)

{

    int i=0;

    int t1,t2;

    char s1[15],s2[15];

    node *root = (node *)malloc(sizeof(node));

    for(i=0; i<26; ++i)

        root->next[i] = NULL;

    root->num = -1;

    id = 0;

    memset(du,0,sizeof(du));

    memset(set,-1,sizeof(set));

    for(i=0; i<n; ++i)

    {

        scanf("%s %s",s1,s2);

        t1 = Trie(root,s1);

        t2 = Trie(root,s2);

        du[t1]++;

        du[t2]++;

        bing(t1,t2);

    }

    BFS(root);

}

int main()

{

    int T;

    int i,n;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        getchar();

        if(n==0)

        {

            printf("Possible\n");

            continue;

        }

        Date_process(n);

        bool flag = true;

        int k = find(0);

        for(i=0; i<id; ++i)

        {

            if(find(i)!=k)

                flag = false;

        }

        if(!flag)  //若该图不连通，Impossible

        {

            printf("Impossible\n");

            continue;

        }

        int ans=0;

        for(i=0; i<id; ++i)

        {

            if(du[i]%2==1)

                ans++;

        }

        if(ans==2 || ans==0)  //欧拉回路或者欧拉路径 Possible

            printf("Possible\n");

        else

            printf("Impossible\n");

    }

    return 0;

}

int Trie(node *root,char *s)  //字典树

{

    int i=0;

    node *p=root;

    while(s[0]!='\0')

    {

        if(p->next[s[0]-'a']==NULL)

        {

            node *tt;

            tt = (node *)malloc(sizeof(node));

            tt->num = -1;

            for(i=0; i<26; ++i) tt->next[i] = NULL;

            p->next[s[0]-'a'] = tt;

            p = tt;

        }

        else

            p = p->next[s[0]-'a'];

        s++;

    }

    if(p->num==-1)

        p->num = id++;

    return p->num;

}

void BFS(node *root)  //深搜释放内存

{

    int i;

    if(root==NULL) return ;

    for(i=0; i<26; i++)

    {

        if(root->next[i]!=NULL)

            BFS(root->next[i]);

    }

    free(root);

}