hdu 5215 Cycle(交叉染色法判断无向图的奇偶环)

hdu 5215

思路:询问一个无向图,是否存在奇数环,以及是否存在偶数环。(不同的环之间可以由相同的点,不能有相同的边)

思路:一开始的想法是,根据染色的奇偶性,如果染色到某个之前染色过的点,和当前要染的颜色相同,说明存在奇数环,不同,说明存在偶数环。

感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的,不同的环之间由相同的点的情况。

比如这组数据:

5 6

1 2

2 3

3 1

1 4

4 5

5 1

两个三元环扣在一起。

实际上是既有奇数环,又有偶数环的。

但是按照我的做法,由于每次只去染没有染过的点,无法发现偶数环。

因此正解是增加一步回溯,这样使得之前存在与某个环中的点还可以出现在其他环中。

然而这样复杂度会炸。。。

于是我们根据,每条边只能走一次,对边加一个vis,使得每条边只走一次,从而保证复杂度。

好题!

这道题我看到了三种解法,第一种是官方解法,tarjan什么(没仔细看)。

第二种是交叉染色。

但是我们可以发现,在这样的情况下,偶环是否和奇环是有联系的,即能不能根据两个奇环的关系,来判断偶环是否存在。

做法:判断是否存在一个点,同时属于两个奇环,如果存在,那么这两个奇环一定可以构成偶环。

证明:令两个奇环分别有x1、x2条边,如果两个环存在一个公共点,令他们存在y条公共边,则它们合并成的环有x1+x2-2*y条边,一定是偶环。因为题目中限制的是边的通过次数,所以即使像下面这组数据一样y=0,偶环是交叉的,也是符合题意的。

 
第二种做法

但是代码略长,而且还要记录路径。

第三种做法就是我这里用到的做法。。。感觉很完美。。可以当模板23333

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz