Description
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
Input
Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.
Output
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
解题报告和代码实现如下：
思路相当清晰
- /*
- 解题报告： http://blog.csdn.net/clearriver/archive/2009/10/13/4665552.aspx
- 学会了基本的trie，并查集使用。
- 这道题大意是：已知有n根木棒，每个木棒有两种颜色表示两端，
- 问：能不能将所有的木棒连接成一条直线（连接处颜色相同）。
- 重点在与知道欧拉通路的概念和性质
- 可以考虑无向图的欧拉通路问题：将每种颜色看成图中的一个节点，木棒看作连接节点的边，于是判断两点：
- 1，每种颜色（节点）的度, G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
- 2，是否为连通图
- 第一点可以通过trie树或则hash来解决。
- 第二点可以通过并查集来实现。
- 首先，每种颜色的度可以通过每条木棒的两端颜色的累积得到，
- 问题是，每种颜色都是字符串，怎么关联每种颜色和度呢？
- 最容易想到的是Hash，这肯定是可行的。例如degree [ hash(red) ]=5。表示颜色为红色的度为5。
- 但是，既然提示用trie树来做，那么trie树的节点的数据域就可以保存每种颜色的id（相当于分配的hash值，
- 可以通过一个全局变量自增产生），这样经过将每种颜色字符串插入到tree中以后，
- 通过trie树的search操作就能高效的获取每种颜色对应的id，每次插入一种颜色，为其产生一个id，
- 只需要注意相同颜色插入时的处理即可。
- 其次，判断无向图是否连通可以使用并查集来判定：经过n-1各union操作后，所有节点都在一个集合
- （树形结构表示集合的话，即所有节点的父节点（集合代表）都一样）。由于每种颜色是由字符串来标示的，
- 每个集合保存颜色对应的唯一id。
- 通过上面两个步骤的判定，就可以得出结果。
- */
- #include <iostream>
- #include <cstring>
- #include <stdlib.h>
- #include <stdio.h>
- #define MAX 500004
- using namespace std;
- char s1[15], s2[15];
- //trie树
- //用于记录每个color字符串对应的序号ID
- //每次执行insert操作都会返回一个ID，这个就是该字符串对应的ID
- // 同时还要一个数组，来使ID与颜色出现的个数对应上
- //最后如果只有两个奇数的点才可以，否则输出impossible
- int degree[MAX];
- struct TreeNode
- {
- int ID;
- bool term;
- TreeNode* next[27];
- TreeNode()
- {
- ID = -1;
- term = false;
- int i;
- for(i = 0; i< 27; i++)
- next[i] = NULL;
- }
- }* root;
- int num = 0;
- int search(char* s, TreeNode* root)
- {
- TreeNode* p = root;
- if(p == NULL) return -1;
- int i = 0, l = strlen(s);
- for(i = 0; i< l; i++)
- {
- if(p->next[s[i] - 'a']== NULL) return -1;
- else p = p->next[s[i] - 'a'];
- }
- if(p->term == true) return p-> ID;
- else return -1;
- }
- int insert(char* s, TreeNode* root)
- {
- TreeNode* p = root;
- int t = search(s, root);
- if(t > 0) return t;
- int i = 0, l = strlen(s);
- for(; i< l; i++)
- {
- if(p->next[s[i] - 'a'] == NULL)
- p->next[s[i] - 'a'] = new TreeNode;
- p = p->next[s[i] - 'a'];
- }
- p->term = true;
- num ++;
- p->ID = num;
- return p->ID;
- }
- //并查集
- //用于判断整张图的联通性，如果到最后边都输入完了之后，还是存在着多个集合
- //说明并不是连通图，输出impossible。
- int parent[MAX];
- int rank[MAX];
- void intial()
- {
- int i;
- for(i = 0; i < MAX; i++)
- { parent[i] = i;
- rank[i] = 1;
- degree[i] = 0;
- }
- }
- int find(int x)
- {
- if(parent[x] != x)
- parent[x] = find(parent[x]);
- return parent[x];
- }
- void merge(int x, int y)
- {
- if(rank[x] > rank[y])
- parent[y] = x;
- else if(rank[y] < rank[x])
- parent[x] = y;
- else
- {
- rank[y] ++;
- parent[x] = y;
- }
- }
- int main()
- {
- //初始化trie树和并查集
- root = new TreeNode;
- intial();
- while(scanf("%s %s", s1, s2) != EOF)
- {
- //每次插入得到ID号，同时令degree[ID]++;
- int id1 = insert(s1, root);
- int id2 = insert(s2, root);
- degree[id1] ++;
- degree[id2] ++;
- //通过得到ID号，运用并查集，来求出组号GID
- int gid1 = find(id1);
- int gid2 = find(id2);
- if(gid1 != gid2)
- {
- merge(gid1, gid2);
- }
- }
- ////if the num of nodes whose degree is odd are more than 2
- int i ,j;
- int noood = 0;
- for(i = 1; i<= num; i++)
- {
- if(degree[i] % 2 == 1) noood ++;
- if(noood > 2)
- {
- cout << "Impossible" << endl;
- return 0;
- }
- }
- ////if the g is joint.
- int gnum = parent[1];
- for(i = 1; i<= num; i++)
- {
- if(gnum != parent[i])
- {
- cout << "Impossible" << endl;
- return 0;
- }
- }
- cout << "Possible" << endl;
- return 0;
-
}