边的双连通分量 395 冗余路径 _连通分量

2. 思路分析：
分析题目可以知道我们需要使得每一对点之间都存在两条相互分离的路径（也即任意两点一定包含两条不相交的路径），由这个特点可以知道其实原问题等价于我们至少需要加多少条边使其变成一个边的双连通分量，这里有一个结论是将原图缩点之后会变成一棵树，那么树中度数为1的节点个数count除以2向上取整就是需要至少加的边的数目，也即（count + 1）/ 2==> 向下取整，这个结论的证明比较复杂，在使用的时候记住即可。因为是无向连通图所以经过算法求解边的双连通分量，缩点之后最终会变成一棵树（将每一个边的双连通分量看成是一个点）。类似于有向图的强联通分量求解方法，我们也需要借助于一个栈stk来记录当前遍历的节点，将找到的边的双连通分量中的所有点记录在对应边的双连通分量idx编号中，在递归调用方法的过程中找到每一条桥，因为使用的是语言所以需要使用列表rec来记录桥的两个节点编号，当求解完边的双连通分量之后将所有桥的两个端点所在的边的双连通分量编号的度数加1，最终遍历一下所有边的双连通分量，计算度数为1的节点个数，也即树中叶子节点的个数count即可，最终(count + 1) / 2就是答案：
3. 代码如下：
【边的双连通分量395 冗余路径】from typing import Listclass Solution:# 定义无向图的tarjan算法需要使用到的全局变量stk, idx, timestamp, top, dcc_cnt, rec = None, None, None, None, None, None# u表示当前遍历的节点,fa表示当前遍历节点的父节点 def tarjan(self, u: int, fa: int, dfn: List[int], low: List[int], g: List[List[int]]):dfn[u] = low[u] = self.timestamp + 1self.timestamp += 1self.stk[self.top + 1] = uself.top += 1for next in g[u]:if dfn[next] == 0:self.tarjan(next, u, dfn, low, g)low[u] = min(low[u], low[next])# 当前节点无法到达祖先节点所以边: u<-->next是桥if dfn[u] < low[next]:# 因为需要记录点所以需要使用列表来记录桥的两个端点, 而使用字典来记录会忽略掉一些重复值导致答案错误, 下面记录的是桥的两个端点self.rec.append(u)self.rec.append(next)# 需要注意下一个点不等于父节点才可以更新low[u]elif next != fa:low[u] = min(low[u], dfn[next])# 找到一个边的双连通分量将其所有点记录在对应边的双连通分量编号中if dfn[u] == low[u]:self.dcc_cnt += 1while True:t = self.stk[self.top]self.top -= 1self.idx[t] = self.dcc_cntif t == u: breakdef process(self):n, m = map(int, input().split())g = [list() for i in range(n + 10)]for i in range(m):a, b = map(int, input().split())# 因为是无向边所以要记录两个方向g[a].append(b)g[b].append(a)dfn, low = [0] * (n + 10), [0] * (n + 10)self.stk, self.idx = [0] * (n + 10), [0] * (n + 10),self.top = self.timestamp = self.dcc_cnt = 0# 使用列表来记录桥self.rec = list()# 因为保证图是连通的所以只需要从1号点调用tarjan方法即可遍历到所有的点self.tarjan(1, -1, dfn, low, g)count = 0d = [0] * (self.dcc_cnt + 1)# 遍历记录的桥的两个端点, 对应的边的双连通分量编号的度数加1for x in self.rec:d[self.idx[x]] += 1for i in range(1, self.dcc_cnt + 1):# 计算叶子节点的个数if d[i] == 1: count += 1# 无向图需要添加(count + 1) / 2条边使其变成边的双连通分量return (count + 1) // 2if __name__ == "__main__":print(Solution().process())