poj2513Colored Sticks（无向图的欧拉回路）

/*
   题意：将两端涂有颜色的木棒连在一起，并且连接处的颜色相同！
   思路：将每一个单词看成一个节点，建立节点之间的无向图！判断是否是欧拉回路或者是欧拉路

   并查集判通 + 奇度节点个数等于2或者0
*/
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 2500005*2
using namespace std;

int f[N];
int trie[N][26];
int rank[N];
int deg[N]; 

int getFather(int x){
   return x==f[x] ? x : f[x]=getFather(f[x]);
} 

void Union(int a, int b){
    int fa=getFather(a), fb=getFather(b);
    if(fa!=fb){
        if(rank[fa]>rank[fb]){
           rank[fa]+=rank[fb]+1;
           f[fb]=fa;
        }
        else{
            f[fa]=fb;
            rank[fb]+=rank[fa]+1;
        }
    }
} 

int main(){
   int cnt=0, c=0, cur=0;
   int u, v;
   char ch[15];
   for(int i=1; i<N; ++i)
      f[i]=i;
   while(scanf("%s", ch)!=EOF){
       ++c;
       cur=0;
       for(int i=0; ch[i]; ++i){
           if(!trie[cur][ch[i]-'a'])
              trie[cur][ch[i]-'a']=++cnt;
           cur=trie[cur][ch[i]-'a'];
       }
       if(c&1)  u=cur;
       else v=cur;

       if((c&1)==0){
          Union(u, v);
          ++deg[u];
          ++deg[v];
      }
   }
   int rootN=0, degN=0;
   for(int i=1; i<=cnt; ++i){
         if(deg[i] && f[i]==i) ++rootN;
         if(deg[i]&1) ++degN;
         if(rootN>1 || degN>2) break;
   }
   if(rootN==1 && (degN==0 || degN==2) || rootN==0 && degN==0)
       printf("Possible\n");
   else printf("Impossible\n");
   return 0;
}