Colored Sticks
Time Limit : 10000/5000ms (Java/Other) Memory Limit : 256000/128000K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Problem 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
题目大意:给你很多对单词,单词相当于一个点,一对单词相当于一条边,问这么多对的单词能否组成一条欧拉路,要求每条边都要经过。题目数据很大,每个单词最多10个字母,之前用map映射,把字母映射成编号,但是速度太慢,一直TLE,后来换成字典树,字典树速度才行,连通性就用并查集,判断欧拉路是否组成,就看度数是奇数的个数是否是0或者2。
代码:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <map>
using namespace std;
struct node
{
int x;
node *next[26];
};
int deg[510005], father[510005], cnt, ant;
node *root, memory[5100050];
node *create()
{
node *p = &memory[ant++];
int i;
for(i = 0; i < 26; i++)
{
p->next[i] = NULL;
}
return p;
};
void insert(char *s, int x)
{
node *p = root;
int i, k;
for(i = 0; s[i]; i++)
{
k = s[i] - 'a';
if(p->next[k] == NULL)
{
p->next[k] = create();
}
p = p->next[k];
}
p->x = x;
}
int search(char *s)
{
node *p = root;
int i, k;
for(i = 0; s[i]; i++)
{
k = s[i] - 'a';
if(p->next[k] == NULL) return 0;
p = p->next[k];
}
return p->x;
}
void init()
{
int i;
for(i = 1; i <= 510000; i++)
{
father[i] = i;
}
memset(deg, 0, sizeof(deg));
cnt = 0;
}
int find(int x)
{
if(x != father[x])
{
father[x] = find(father[x]);
}
return father[x];
}
void Union(int x, int y)
{
father[x] = y;
}
bool judge() //判断是否满足欧拉
{
int i, k, odd = 0;
for(i = 1; i <= cnt; i++)
{
if(deg[i]%2 == 1) odd++;
}
if(odd != 0 && odd != 2) return false;
k = find(1);
for(i = 2; i <= cnt; i++)
{
if(k != find(i)) return false;
}
return true;
}
int main()
{
int x, y, fx, fy;
char s1[15], s2[15];
init();
root = create();
while(scanf("%s %s", s1, s2) != EOF)
{
x = search(s1); //映射求编号速度太慢
y = search(s2); //用字典树来求编号
if(x == 0) insert(s1, x = ++cnt);
if(y == 0) insert(s2, y = ++cnt);
deg[x]++;
deg[y]++;
fx = find(x);
fy = find(y);
if(fx != fy) Union(fx, fy);
}
if(judge()) printf("Possible\n");
else printf("Impossible\n");
return 0;
}
分享到:
相关推荐
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
北大POJ1011-Sticks 解题报告+AC代码
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
poj 2978 Colored stones.md
Catenyms poj hoj 欧拉回路输出路径
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
详细解释 ,既有源代码又有书面文字解释,ppt,在VC6上完成
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
poj 2452 Sticks Problem.md
北大POJ1159-Palindrome 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
这份代码用C++实现了经典算法并查集,来源于poj题目1182
北大POJ2002-Squares 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ1837-Balance 解题报告+AC代码
北大POJ2503-Babelfish 解题报告+AC代码
北大POJ1201-Intervals 解题报告+AC代码
北大POJ1039-Pipe 解题报告+AC代码