边的双连通分量的性质: 1)对于一个边双连通分量,不管删除那一条边,它都是连通的。 2)对于一个边连通分量,任意两点之间至少包含两条不想交路径(两条路径舞公共边但可以有公共点)这是一个充要条件。 这代本质是:对于一个无向图来说最少加多少条边可以让这个无向图变成边的双连通分量。 结论:把这个图变成边的双连通分量森林,每个e-dcc都看成一个点,假设度为1的点为cnt那么答案就是 (cnt + 1) / 2. 注意:与请联通分量不同的是建图的时候枚举边更方便。