hdu 5215 思路:询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以由相同的点，不能有相同的边） 思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。 感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的，不同的环之间由相同的点的情况。 比如这组数据： 5 6 1 2 2 3 3 1 1 4 4 5 5 1 两个三元环扣在一起。 实际上是既有奇数环，又有偶数环的。 但是按照我的做法，由于每次只去染没有染过的点，无法发现偶数环。 因此正解是增加一步回溯，这样使得之前存在与某个环中的点还可以出现在其他环中。 然而这样复杂度会 …

poj3310 题目链接 题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过 环的话并查集就好。。 关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长？ 于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。 具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一 …

hdu4514 题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。 思路：无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。 但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。 也就是要在一个不联通的图中求最长路径。。。 没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。 不过感觉最容易想到的还是求多次直径的做法。。。 也就是。。每一个联通块求一次直径。。。取最大。。。 具体做的时候。。。加一个bool数组在bfs标记一下就好。。。 以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注 …