Colored Sticks
DescriptionYou 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?InputInput 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.OutputIf the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.Sample Inputblue redred violetcyan blueblue magentamagenta cyanSample OutputPossible题目大意:
给定一些木条,木条的两头都有颜色,颜色相同的两根木条可以相连,问是否可以连成一条直线。
解题思路:
其实就是问是否可以构成欧拉路径。这里给出欧拉路径的定义。
若图G中存在这样一条路径,使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈,则称为欧拉(Euler)回路。(即一笔画问题)
存在欧拉路径的成分必要条件为:一个无向图存在欧拉回路,当且仅当该图只存在0或2个奇数入度数的顶点,且该图是连通图。
1)判断 奇数度数的个数
很好搞定,建立一个数组存放每个节点的入度,建图结束后遍历即可。
2)判断是否为连通图
使用并查集和路径压缩来做。若路径压缩之后每个点都有着相同的父节点(即每个点都有相同的祖先节点)。说明图连通。
Trie树的应用
由于该题的Node为字符串,建图的时候会比较困难。使用map映射会超时,所以使用Trie树来进行映射。具体实现请看代码备注。
Code:
1 /************************************************************************* 2 > File Name: poj2513.cpp 3 > Author: Enumz 4 > Mail: 369372123@qq.com 5 > Created Time: 2014年10月26日 星期日 20时16分17秒 6 ************************************************************************/ 7 8 #include9 #include 10 #include 11 #include 12 #include 13 #include 14 #include
15 #include 16 #include