本来我是dfs的时候直接把一个连通块的所有结点push到vector,然后判断size为1的,但这样行不通。
如果不新建图的话,有的连通块在缩点后度为1,但以上做法明显可以不为 1.
比如 1 2 一个块, 3 4 一个块, 5 6 一个块,他们的size都是2,但答案是 1 2 那个块要和 5 6 的块连,所以必须缩点,新建边。
关于缩点,我看了一些题解,我这里有一种新的方法。还是 dfs ,把每个连通块的所有结点弄成一个编号,每个结点新编号记作block_i。然后在写个 dfs,如果搜到了桥,直接把 block_u 与 block_v 相连。一下子都完美解决了。当然,上述 2 个 dfs 都不能往回搜,要记录 vis。
为什么这样建不会有重复的,对于一个连通块,不可能有其他的连通块的编号两次出现在这里。假设有,那么这两个连通块应该是一个连通块,假设不成立。
最后在遍历 size == 1 就 ok 啦,这样写不要忘记最开始判断重边。