algorithm - 最大化连接图中要切割的边数

Question

这个问题与Leetcode 的“网络中的关键连接”非常相似。给定一个无向图，我们想要找到所有的桥。无向连通图中的一条边是一座桥，当且仅当当且仅当移除它会断开该图。

变体

我不想找到所有的桥梁，而是想最大化要删除的边数，以便图形保持连接。

示例 1

Input: n = 5, edges = [[1, 2], [1, 3], [3, 4], [1, 4], [4, 5]]

Output: 1

首先，我可以删除[3,4],[1,3]或[1,4]. 接下来，在去除 3 条边中的任何一条后，剩下的边都是桥。因此，为了使图保持连接，要删除的最大边数为 1。

示例 2

Input: n = 6, edges = [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [4, 6], [5, 6]]

Output: 2

Answer 1

这很容易，如果我们在连通图中有E边和N节点，我们可以删除E-N+1边，以便图保持连通。

这个怎么做？：

只需执行 DFS/BFS 即可找到图的任何生成树，因为生成树是连接的，我们可以删除所有其他边。