poj 2513 Colored Sticks trie树+欧拉图+并查集

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

点击打开链接

Description

Input

Output

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible

Hint

一开始想用map建立字符串和数字的映射，然后用并查集判断联通，欧拉图判断是否可以构成一笔画问题，但是最后超时了，网上一查才知道必须用trie建立映射关系才能过

因为字符最多10位，那么树的深度最多10层，映射任何一个字符串都可以在近似常数时间内完成，效率非常高

先附上map实现的TLE的代码：

#include<stdio.h>
#include<string>
#include<map>
using namespace std;
int father[500010];
int degree[500010] = {0};
//int *root[26]; //
int getfather(int i)
{
if(father[i] == 0)
return father[i] = i;
else if(father[i] == i)
return i;
else
return father[i] = getfather(father[i]);
}
void mergeset(int a, int b)
{
a = getfather(a);
b = getfather(b);
father[a] = b;
}
int main()
{
//freopen("in.txt", "r", stdin);
map<string, int> color;char color1[20], color2[20];
int total = 0;
while(scanf("%s%s", color1, color2) != EOF)
{
int a, b;
if(color[color1] == 0)
a = (color[color1] = ++total);
if(color[color2] == 0)
b = (color[color2] = ++total);
degree[a] ++;
degree[b] ++;
mergeset(a, b);
}
int i;
int fa = getfather(1);
bool flag = 0;
int count = 0;
//for(i = 1; i <
for(i = 1; i <= total; i++)
{
if(getfather(i) != fa)
break;
if(degree[i] % 2 != 0)
{
count ++;
if(count > 2)
break;
}
}
if(i <= total || count == 1)
printf("Impossible\n");
else
printf("Possible\n");return 0;
}

可以发现map省事很多，但是效率不高

这是trie图的AC代码：1250MS

#include<stdio.h>
#include<string>
#include<iostream>
#include<map>
using namespace std;
int father[500010];
int degree[500010] = {0};struct Node
{
int num;
Node *next[26];
Node()
{
num = 0;
int i;
for(i = 0; i < 26; i++)
next[i] = 0;
}
};
Node root[26];
int total;
int getnum(char * str, Node * node)//getnum函数既可以插入也可以获取，如果没有这个单词就建立一个，如果有了就返回这个单词的编号
{
if(*str == 0)
{
if(node->num != 0)
return node->num;
else
return node->num = ++total;
}
if(node->next[*str - 'a'] == 0)
node->next[*str - 'a'] = new Node;
return getnum(str + 1, node->next[*str - 'a']);
}
int getfather(int i)
{
if(father[i] == 0)
return father[i] = i;
else if(father[i] == i)
return i;
else
return father[i] = getfather(father[i]);
}
void mergeset(int a, int b)
{
a = getfather(a);
b = getfather(b);
father[a] = b;
}
int main()
{
//freopen("in.txt", "r", stdin);
char color1[20], color2[20];
while(scanf("%s%s", color1, color2) != EOF)
{
int a = getnum(color1 + 1, &root[*color1 - 'a']), b = getnum(color2 + 1, &root[*color2 - 'a']);
degree[a] ++;
degree[b] ++;
mergeset(a, b);
}
int i;
int fa = getfather(1);
bool flag = 0;
int count = 0;
for(i = 1; i <= total; i++)
{
if(getfather(i) != fa)
break;
if(degree[i] % 2 != 0)
{
count ++;
if(count > 2)
break;
}
}
if(i <= total || count == 1)
printf("Impossible\n");
else
printf("Possible\n");return 0;
}