math - 如果添加新边，图的强连通分量的数量如何变化

Question

练习:22.5-1 CLRS
如果一个新的图的强连通分量的数量如何变化
边缘被添加？

Somewhere给出的答案是如果添加新边，可能会发生两种情况之一。
1) 如果新边连接属于强连通分量的两个顶点，则强连通分量的数量将保持不变。
2) 相反，如果边连接两个强连接分量，并且边与两个分量之间现有路径的方向相反，则将创建一个新的强连接分量，增加分量的数量。
我认为第二点是不正确的。
假设我们有两个强连通分量 C 和 C'
a) 如果它们之间不存在边或边 C->C' 并且新边连接为 C->C' 则什么都不会发生。
b) 如果它们之间存在边 C->C' 并且新边连接为 C'->C，则 C' 将合并到 C，将强连接组件的数量减少 1，因为每个顶点都可以相互到达。
如果我错了，请纠正我。

Answer 1

你完全正确。您引用的答案在其描述中是错误的:添加边只会减少强连接组件的数量。一旦添加了所有可能的边，就只剩下一个强连接组件——整个图。