最新消息:点击查看大S的省钱秘笈

POJ 2513 Colored Sticks C语言版

POJ题解 Slyar 122浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

Trie树+并查集+欧拉通路

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

Slyar:说下题目大意,给出n根木棍,每根木棍两端都有颜色,颜色为小于10的字符串,问能否将所有的木棍排成一排,使得每两根木棍衔接的地方颜色相同。

这题我一开始暴力做,很随意的就TLE了...看了Discuss发现要用什么"Trie"和"欧拉通路",还要用到前几天学会的并查集...晕死,根本不知道什么是"Trie"和"欧拉通路",遂Google了一下,得知"Trie"俗称字典树,具体内容完了发到博客上...欧拉通路完了也发博客上...本文发表2 weeks后应该可以搜索到...

对于知道以上概念者,可以看出本题就是将所有的颜色看做节点,连接两种颜色的木棍看做节点之间的连边,判断无向图中是否存在欧拉通路,判断条件是:

1、有且只有两个度为奇数的节点

2、图是连通的

由于节点是字符串,因此我们可以利用字典树将其转换成一个颜色序号。这样,统计每种颜色的出现次数就可以了。判断图是否连通,可以利用并查集:若最后所有节点在同一个集合,则图是连通的。

eg. blue (magenta magenta) (cyan cyan) (blue blue) (red red) violet

转载请注明:Slyar Home » POJ 2513 Colored Sticks C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (5)

  1. ORZ!!膜拜楼主!!!
    菜鸟一号5年前 (2011-08-11)回复
  2. QRZ!!楼主强大!!
    匿名5年前 (2011-08-10)回复
  3. @Slyar 努力的小盆友,粉有前途。。。
    Felix0218年前 (2009-06-12)回复
  4. @Felix021, 呃...在学习算法...
    Slyar8年前 (2009-06-12)回复
  5. Slyar童鞋最近狂刷POJ阿。
    Felix0218年前 (2009-06-12)回复