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

How do I find the minimum extra amount of edges needed to complete a connection?

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

输入示例:

4 2(节点和边)

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

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

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

连接图表所需的最小连接数为 N-1。但如果不存在连接数为 0 的节点,这仍然成立。

尝试想象一条类似于连通列表设计的路径。除两端外,每个节点的度数正好为 2。这样(假设您的连接不是定向的),从任何节点开始,您只需访问下一个尚未访问的节点即可到达目标。

如果 M>N-1,那么您可以搜索连接数超过需要的节点,然后从那里继续。

尝试计算额外的连接数,并将其与所需的最小连接数 (N-1) 进行比较。

您只需要:

1) 求连通分量。可以通过 dfsbfs 来完成。在您的示例中,这些组件分别是 0, 12, 3

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

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