pku 2513 Colored Sticks Trie树+并查集+欧拉回路(半欧拉回路)

时间：2011-05-06 来源：奋斗青春

题目意思：有许多的棍子，每一个棍子的两个端点都标记一种颜色，端点颜色相同的两个棍子可以连在一起，问最后能不能把所有的棍子连成一条直线。。

刚开始题目理解错误，，误以为最后连成一个环，怎样搞都不对，，后来用有道才发现理解错误，，英语差的真的伤不起啊。。。

先用Trie树把颜色改为点，并记录每一种颜色出现的次数，再用并查集判断是否连通，，之后用欧拉回路判断能否构成直线。。

这里存在两种情况：

1-3 ， 3-5, 5-1 和 1-3 ， 3-5， 5-1 ， 1-2

一种是所有的所有的颜色都出现偶数次，

另一种是有两种颜色出现奇数次，，这样就很简单了。。

# include<stdio.h>
# include<string.h>
# define N 250005
# define MAX 26
struct Trie{
        int num,xuhao;
        struct Trie *next[MAX];
};
int t,adj[2*N],father[2*N];
Trie *NewTrie()
{
        Trie *temp=new Trie;;
        int i;
        temp->num=0;
        for(i=0;i<MAX;i++)
                temp->next[i]=NULL;
        return temp;
}
int updata(Trie *p,char s[])
{
        int len,i;
        Trie *temp=p;
        len=strlen(s);
        for(i=0;i<len;i++)
        {
                if(temp->next[s[i]-'a']==NULL) temp->next[s[i]-'a']=NewTrie();
                temp=temp->next[s[i]-'a'];
        }
        temp->num++;
        if(temp->num==1) {t++;temp->xuhao=t;adj[t]=1;}
        else adj[temp->xuhao]++;
        return temp->xuhao;
}
int find(int x)
{
        while(father[x]!=x)
                x=father[x];
        return x;
}
void Union(int a,int b)
{
        int x,y,min;
        x=find(a);
        y=find(b);
        min=x<y?x:y;
        father[x]=father[y]=father[a]=father[b]=min;
}
int main()
{
        int i,count,flag,a,b;
        char s1[15],s2[15];
        Trie *p;
        p=NewTrie();
        t=0;
        for(i=0;i<2*N;i++)
                father[i]=i;
        while(scanf("%s%s",s1,s2)!=EOF)
        {
                a=updata(p,s1);
                b=updata(p,s2);
                Union(a,b);
        }
        count=0;
        flag=0;
        for(i=1;i<=t;i++)
        {
                if(father[i]!=1) {flag=1;break;}
                if(adj[i]%2!=0) count++;
                if(count>=3) {flag=1;break;}
        }
        if(flag==1) printf("Impossible\n");
        else printf("Possible\n");
        return 0;
}