题目地址：
题意就是给我们n个带颜色的木棍，看是否能排成一排（相接的颜色必须是一样的），
解题思路是看的别人的：判断无向图中是否存在欧拉通路，判断条件是：
1、有且只有两个度为奇数的节点
2、图是连通的
由于节点是字符串，因此我们可以利用字典树将其转换成一个颜色序号。这样，统计每种颜色的出现次数就可以了。判断图是否连通，可以利用并查集：若最后所有节点在同一个集合，则图是连通的。
#include#include #include #define maxn 501000int father[maxn],degree[maxn];struct node{ int flg; int num; node *next[26];}*root;int n;int insert(char *str){//进行动态创建的插入。 node *p = root,*q; int m; while(*str) { m = *str - 'a'; str ++; if(p->next[m] != NULL) p = p->next[m]; else { q = (node*)malloc(sizeof(node)); memset(q->next,NULL,sizeof(q->next)); q->flg = 0; q->num = -1; p->next[m] = q; p = q; } } p->flg = 1; return p->num = n++;}int search(char str[]){//查找操作，查看字符串是否已经存在 int m,len = strlen(str); node *p = root; for(int i = 0; i < len; i++) { m = str[i] - 'a'; if(p->next[m] == NULL)//不存在则将str插入到字典树中， return insert(str); p = p->next[m]; } //当前位置为单词结尾，则返回单词的编号,否则将单词插入到字典树中 if(p->flg) return p->num; else return insert(str);}int find(int x)//并查集查找祖先节点{ if(x != father[x])//递归路径压缩 father[x] = find(father[x]); return father[x];}void merge(int x,int y) {//并查集的合并操作 x = find(x); y = find(y); if(x != y) father[x] = y;}int main(){ char str1[11],str2[11]; int x,y,i,k; bool flg; n = 0; for(i = 0; i < maxn ; i++) father[i] = i; root = (node*)malloc(sizeof(node)); memset(root->next,NULL,sizeof(root->next)); while(scanf("%s%s",str1,str2) != EOF) { x = search(str1); y = search(str2); merge(x,y); degree[x]++; degree[y]++; } k = 0; for(i =0; i < n; i++) {//查找奇度顶点 if(degree[i]%2) k++; } flg = true; if(k > 2)//当奇度顶点数大于2个的时候则不存在欧拉回路和欧拉通路 flg = false; else { k = find(0); //判断图是否连通， for(i = 1; i < n && flg; ++i) if(find(i) != k) flg = false; } //当图存在欧拉通路或者欧拉回路则输出Possible否则输出Impossible if(flg) printf("Possible\n"); else printf("Impossible\n"); return 0;}