http://poj.org/problem?id=2513
题意：给一些木棒，木棒两端图上颜色，将端点颜色相同的木棒连在一起，问是否能连成一条直线。
思路：将两端的颜色看成点，将木棒看成边，判断是否构成欧拉路。
欧拉路：图G，若存在一条路，经过G中每条边有且仅有一次，称这条路为欧拉路，如果存在一条回路经过G每条边有且仅有一次，
称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。
判断欧拉路是否存在的方法
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
判断欧拉回路是否存在的方法
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。
其中判断图的连通性用并查集。
1 #include <stdio.h> 2 #include <string.h> 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]!=' ') 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 "); 80 return 0; 81 } 82 } 83 printf("Possible "); 84 return 0; 85 }