题意：给一些木棒，木棒两端图上颜色，将端点颜色相同的木棒连在一起，问是否能连成一条直线。

思路：将两端的颜色看成点，将木棒看成边，判断是否构成欧拉路。

欧拉路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，

称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。

判断欧拉路是否存在的方法

有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通，所有的顶点出度=入度。

无向图：图连通，所有顶点都是偶数度。

其中判断图的连通性用并查集。

1 #include 
      
        2 #include 
       
         3  4 const int N=500050; 5 using namespace std; 6  7 struct trie 8 { 9     int id;10     trie *next[26];11     trie()12     {13         id = 0;14         for (int i = 0; i < 26; i ++)15             next[i] = NULL;16     }17 }*root;18 int degree[N];19 int f[N],cnt;20 void init()21 {22     for (int i = 0; i < N; i ++)23     {24         degree[i] = 0;25         f[i] = i;26     }27     cnt = 0;28 }29 int find(int x)30 {31     if (x!=f[x])32         f[x] = find(f[x]);33     return f[x];34 }35 void merge(int x,int y)36 {37     x = find(x);38     y = find(y);39     f[x] = y;40 }41 int find_id(char s[])42 {43     int i = 0;44     trie *p = root;45     while(s[i]!='\0')46     {47         if (p->next[s[i]-'a']==NULL)48             p->next[s[i]-'a'] = new trie;49         p = p->next[s[i++]-'a'];50     }51     if (p->id==0)52         p->id = ++cnt;53     return p->id;54 }55 int main()56 {57     //freopen("sad.txt", "r", stdin);58     int id1,id2;59     char s1[12],s2[12];60     init();61     root = new trie;62     while(~scanf("%s%s",s1,s2))63     {64 65         id1 = find_id(s1);66         id2 = find_id(s2);67         degree[id1]++;68         degree[id2]++;69         merge(id1,id2);70     }71     int count = 0;72     int father = find(1);73     for (int i = 1; i <= cnt; i ++)74     {75         if (degree[i]%2)76             count++;77         if(count > 2||find(i)!=father)78         {79             printf("Impossible\n");80             return 0;81         }82     }83     printf("Possible\n");84     return 0;85 }