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

 

 

poj 3310 Caterpillar (树的直径+并查集判环+dfs判断连通性)

poj3310 题目链接

题意:给出一个无向图。。。问是否满足。。联通,并且无环,并且能找到一条路径,图中所有的顶点要么在这条路径上,要么与这条路径上的顶点相邻。

思路:一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过

环的话并查集就好。。

关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长?

于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。

具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一个to[]数组表示相连。。。to[u]=v,to[v]=u…

然后只要ok[i]或者ok[to[i]]满足其一就好。。。

又是1A,蛤蛤蛤蛤蛤,我好神啊(误

 

 

 

 

hdu 4514 湫湫系列故事——设计风景线 (无向图并查集判环+非联通图的最长路径)

hdu4514

题意:给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。

思路:无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。

但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。

也就是要在一个不联通的图中求最长路径。。。

没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。

不过感觉最容易想到的还是求多次直径的做法。。。

也就是。。每一个联通块求一次直径。。。取最大。。。

具体做的时候。。。加一个bool数组在bfs标记一下就好。。。

以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注意d数组初始化的问题。。。不能初始化成0x3f…(这么说来即使联通也没必要初始化成0x3f。。。。)

还有一点,这道题数据量比较大。。。用vector存图会MLE …