题意：有一些木棍，木棍的两边各有一种颜色，如果两根木棍的一边颜色相同的话，那么就可以连在一起，问能不能完全连成一根
思路：不在是简单的欧拉路，如果能将颜色表达成一个数字的话就能转化为欧拉路了，
用Trie树来优化，再用并查集判断是否为欧拉路，将pre[]初始化为-1，加快速度
#include #include #include #include #include using namespace std; const int N = 15; const int M = 1000010; struct Trie{ int num; Trie *next[26]; }*Head; Trie trie[M]; char u[N],v[N]; int num,n,top,total,flag; int pre[M],in[M]; int Find_set(int x){ return pre[x] == -1 x : (pre[x] = Find_set(pre[x])); } void Make_Set(int x,int y){ int root1 = Find_set(x); int root2 = Find_set(y); if (root1 != root2) pre[root2] = root1; } int insert(char *str){ Head = &trie[0]; int len = strlen(str); for (int i = 0; i < len; i++){ int temp = str[i] - 'a'; if (Head->next[temp] == NULL) Head->next[temp] = &trie[++num]; Head = Head->next[temp]; } if (Head->num == 0) Head->num = top++; return Head->num; } void init(){ num = total = 0,top = 1,flag = 1; memset(in,0,sizeof(in)); memset(pre,-1,sizeof(pre)); for (int i = 0; i < 20; i++){ trie[i].num = 0; for (int j = 0; j < 26; j++) trie[i].next[j] = NULL; } } int main(){ int tmp,temp; init(); while (scanf("%s %s",u,v) != EOF){ tmp = insert(u),temp = insert(v); in[tmp]++,in[temp]++; Make_Set(tmp,temp); } int root = Find_set(1); for (int i = 1; i < top; i++){ if (root != Find_set(i)){ flag = 0; break; } if (in[i] & 1) total++; if (total > 2) break; } if ((total == 0 || total == 2) && flag == 1) printf("Possible\n"); else printf("Impossible\n"); return 0; }