这道题目是一个模型：给连通的无向图加边，使得无向图没有桥（即变成边双连通分量），最小化加边数
因为边双连通分量本来就没有桥，所以我们考虑对整个图求一遍边双连通分量（使用 tarjan 算法），然后将边双连通分量缩为一个点考虑。那么缩完点后得到的图一定是一棵树（因为图中不可能存在环）
然后要加的边的个数就是\(\lceil\frac{cnt}{2}\rceil\)，其中\(cnt\)是图中度数为\(1\)的点数
先证这是下界，每一次操作顶多使度数为\(1\)的点消失两个，考虑一下最后的细节问题即可
然后构造一下：
直接考虑节点数量在\(2\)以上的情况，我们任选一个度数大于\(1\)的点（一定找得到）作为根节点，然后这棵树就长这个样子：
每个子树都有若干个叶子，数目设为\(a_1\)，\(a_2\)，...，\(a_n\)（假设已经从大到小排好序了）
我们每次选择不同的子树的两个叶子连边，相当于把序列{\(a\)}中选两个数\(-1\)
先假设\(\sum_{i=1}^{n-1}a_i≥a_n\)
我们每次操作都让\(a\)中最大的数和最小的数进行减一（中间注意动态调整），那么最后要么全部变为\(0\)，要么还剩下一个\(1\)
对于前面一种情况，此时就已经符合题意了，对于后面一种情况，此时在让这个叶子节点与根节点进行连边即可，不难算出添加的边数是以上结论给出的式子
如果\(\sum_{i=1}^{n-1}a_i＜a_n\)怎么办？
此时，我们换根，让\(a_n\)所对应的子树的顶点作为根，直到对应的序列满足\(\sum_{i=1}^{n-1}a_i≥a_n\)
证毕
这种每次按照单位数量选两个减的好像都是让最大的和最小的减，然后中途动态调整
标签：连通,子树,边双,sum,路径,节点,冗余,分量 From： https://www.cnblogs.com/dingxingdi/p/18012894