POJ 2513
有N根木棒，一根木棒有2头，我们把每头涂色（相同或不同），如果2根木棒有相同颜色的一端就可以连接，颜色全部不同就不能连接，现在给你N根木棒以及它们的颜色，问最后能不能链接成1条链。
欧拉回路的问题，判断联通 以及 奇点个个数
输入为字符串，开始并不知道怎么弄，参考了下别人的报告，用字典树处理（学到的新东西），
#include#include #include #include #include using namespace std;const int N = 15;const int M = 1000010;struct node{ int num; node* next[26];}*Head;char u[N], v[N];int num, n, top, total;bool flag;int pre[M], in[M];node pnode[M];int fin(int x) //递归+路径压缩{ return pre[x] == -1 ? x : (pre[x] = fin(pre[x]));}void Uni(int x, int y) //合并{ int root1 = fin(x); int root2 = fin(y); if(root1 != root2) pre[root2] = root1;}int insert(char str[]) //返回数组下标{ Head = &pnode[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] = &pnode[++num]; Head = Head->next[temp]; } if(Head->num == 0) Head->num = top++; return Head->num;}void init(){ num = total = 0; top = 1; flag = true; memset(in,0,sizeof(in));memset(pre,-1,sizeof(pre)); for(int i = 0; i 2) break; } // 奇点为0 环 ，奇点为2 链 puts(((total == 0 || total == 2) && flag == true) ? "Possible" : "Impossible"); return 0;}