|
Colored Sticks
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. Sample Input blue red red violet cyan blue blue magenta magenta cyan Sample Output Possible Hint Huge input,scanf is recommended. Source |
解题报告：题意就是给我们n个带颜色的木棍，看是否能排成一排（相接的颜色必须是一样的），
解题思路是看的别人的：判断无向图中是否存在欧拉通路，判断条件是：
1、有且只有两个度为奇数的节点
2、图是连通的
由于节点是字符串，因此我们可以利用字典树将其转换成一个颜色序号。这样，统计每种颜色的出现次数就可以了。判断图是否连通，可以利用并查集：若最后所有节点在同一个集合，则图是连通的。
代码如下：
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> const int MAX = 500010; using namespace std; int father[MAX];//father[x]表示x的父节点 int rank[MAX];//rank[x]表示x的秩 int degree[MAX];//degree记录节点的度 int num = 0;//记录字典树有效节点个数 struct Trie//字典树节点的类型 { int flag; struct Trie *next[26]; }; struct Trie *Root;//字典树的根节点 struct Trie *NewSet()//创建新节点的函数 { int i; struct Trie *p; p = (struct Trie *)malloc(sizeof(struct Trie));//开辟新节点 for (i = 0; i < 26; ++i)//初始化 { p->next[i] = NULL; } p->flag = 0; return p; } int Insert(char *s)//以Root为根插入字符串函数 { int i, len; struct Trie *p; p = Root; len = strlen(s); for (i = 0; i < len; ++i) { //节点不存在时创建新的节点 if (p->next[s[i] - 'a'] == NULL) { p->next[s[i]- 'a'] = NewSet(); } p = p->next[s[i] -'a']; } if (p->flag == 0) { p->flag = ++num;//得到并返回颜色节点序号 } return p->flag; } void MakeSet()//初始化函数 { int i; for (i = 0; i < MAX; ++i) { father[i] = i; rank[i] = 0; degree[i] = 0; } } int Find(int i) { if (father[i] != i)//路径压缩 { father[i] = Find(father[i]); } return father[i]; } void Merge(int x, int y)//合并函数 { int i, j; i = Find(x); j = Find(y); if (i != j) { if (rank[i] > rank[j]) { father[j] = i; } else { if (rank[i] == rank[j]) { rank[j] ++; } father[i] = j; } } } int main() { int i, sum, x, y; char str1[26], str2[26]; MakeSet(); Root = NewSet(); while (scanf("%s%s", str1, str2) != EOF) { x = Insert(str1); y = Insert(str2); degree[x] ++;//度数加一 degree[y] ++; Merge(x, y); } sum = 0;//记录度数为奇数的个数 //求度数为奇数的点的个数 for (i = 0; i < num; ++i) { if (degree[i] % 2) { sum ++; } } int Flag = 1;//假设可以连在一块 //若度大于2则肯定不可能 if (sum > 2) { Flag = 0; } else//判断图是否连通 { for (i = 2; i < num; ++i)//是否所有的点在一个集合中 { if (Find(i) != Find(1))//若不在一个集合中 { Flag = 0; } } } if (Flag) { printf("Possible\n"); } else { printf("Impossible\n"); } return 0; }