POJ 2513 Colored Sticks(字典树 + 并查集 + 欧拉回路)

浅浅的花香味﹌ 2021-11-02 06:32 225阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td> Colored Sticks 
 <div> 
 <table> 
 <tbody> 
 <tr> 
 <td> Time Limit:&nbsp;5000MS </td> 
 <td>&nbsp;</td> 
 <td> Memory Limit:&nbsp;128000K </td> 
 </tr> 
 <tr> 
 <td> Total Submissions:&nbsp;23116 </td> 
 <td>&nbsp;</td> 
 <td> Accepted:&nbsp;6095 </td> 
 </tr> 
 </tbody> 
 </table> 
 </div> 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 <pre>blue red</pre> <pre>red violet</pre> <pre>cyan blue</pre> <pre>blue magenta</pre> <pre>magenta cyan</pre> Sample Output <pre>Possible</pre> Hint Huge input,scanf is recommended. Source <a href="http://poj.org/searchproblem?field=source&amp;key=The+UofA+Local+2000.10.14" rel="nofollow">The UofA Local 2000.10.14</a> </td> 
 </tr> 
 </tbody> 
</table>

解题报告：题意就是给我们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;
 }

转载于:https://www.cnblogs.com/lidaojian/archive/2012/04/12/2444747.html