题意：给定一些木棒，木棒两端都涂上颜色，求是否能将木棒首尾相接，连成一条直线，要求不同木棒相接的一边必须是相同颜色的。
无向图存在欧拉路的充要条件为：
① 图是连通的；
② 所有节点的度为偶数，或者有且只有两个度为奇数的节点。
图的连通可以利用并查集去判断。
度数的统计比较容易。
代码实现
//第一次用指针写trie,本来是用二维数组，发现数组开不下，只好删删改改，改成指针
//做这道题，知道了欧拉回路判定，还有用指针写trie
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 500010;
char s1[15], s2[15];
int fa[N], u, v, in[N], color =1; struct Trie
{
Trie *ch[26];
int val;
void init()
{
for(int i=0; i<26; i++) ch[i] = NULL;
val = 0;
} Trie()
{
for(int i=0; i<26; i++) ch[i] = NULL;
val = 0;
} int idx(char c){return c-'a'; } int ins_find(char *s, Trie *t)
{
int n = strlen(s);
for(int i=0; i<n; i++)
{
int c = idx(s[i]);
if(!t->ch[c])
{
t->ch[c] = new Trie();
}
t = t->ch[c];
}
if(!t->val) t->val = color++;
return t->val;
}
}*tr; int find(int x)
{
if(fa[x]<0) return x;
return fa[x]=find(fa[x]);
} int main()
{
// freopen("in.txt", "r", stdin);
memset(fa, -1, sizeof(fa));
tr = new Trie();
while(scanf("%s%s", s1, s2)>0)
{
u = tr->ins_find(s1, tr), v = tr->ins_find(s2, tr);
in[u]++, in[v]++;
u = find(u), v = find(v);
if(u!=v) fa[u] = v;
}
int num1=0, num2=0; for(int i=1; i<color; i++)
{
if(in[i]&1) num1++;
if(fa[i]==-1) num2++;
}
if((num1==0 || num1==2) && num2<2)
puts("Possible");
else puts("Impossible");
return 0;
}