algorithm - 如何找到完成连接所需的最少额外边数？

Question

假设我们已分别获得节点数和边数 N 和 M。然后我们得到连接了哪些节点。我们如何找到完成连接所需的最少额外边数，以便您可以访问每个节点？通过找到答案，您应该能够遍历每个节点，通过直接进入或通过另一个节点到达目标。

输入示例:

4 2(节点和边)

0 1(节点0和节点1相连)

2 3(节点2和节点3相连)

这应该给我们答案 1，我们需要一条额外的边来完成连接。

Answer 1

您只需要:

1) 找到连接的组件。它可以通过 dfs 或 bfs 来完成。在您的示例中，这些组件分别是 0, 1 和 2, 3。

2) 然后您需要遍历所有组件并为每两个连续组件连接任意两个顶点。通过这种方式，您可以连接第一个和第二个组件，然后连接第二个和第三个组件，依此类推...在您的示例中，您可以将任何顶点 0, 1 与任何顶点 2, 3 连接。例如，您可以连接顶点 0 和 2。

很容易看出，如果分量的总数等于C，那么答案就是C - 1 条附加边。