Colored Sticks
Time Limit: 5000MS |
|
Memory Limit: 128000K |
Total Submissions: 20750 |
|
Accepted: 5482 |
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
要仔细看题,木棍不仅仅只是可以一个方向放置,还可以倒过来,所以简单的说,这个题是一个无向图的欧拉回路判断
但是直接用map要超时。。我先开始就这样TLE了。后来看了下后面的discuss,发现要用字典树
于是又自己手动写了个字典树。
所以综上,我们需要:
1、字典树对每一个字符串进行标号
2、并查集判断整个图是否连通
3、判断无向图的欧拉回路是否存在
我的代码:
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
Catenyms poj hoj 欧拉回路输出路径
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
用Java代码实现POJ(PKU)上题2494!
Hangover Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 44187 Accepted: 20574 Description How far can you make a stack of cards overhang a table? If you have one card, you can create a...
acm pku poj 1000 1001 1002 1003 1201
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
1.把自己的污水排到河里V 2.把自己的污水送到右边> 3.把自己的污水送到左边
这份代码用C++实现了经典算法并查集,来源于poj题目1182