Colored Sticks
| Time Limit: 5000MS | Memory Limit: 128000K | |
| Total Submissions: 27955 | Accepted: 7403 |
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.
一开始想用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;
}