练习:22.5-1 CLRS
如果添加新边,图的强连通分量的数量如何变化?
某处给出的答案是如果添加新的边缘,可能会发生以下两种情况之一。
1)如果新边连接了属于强连通分量的两个顶点,则强连通分量的个数保持不变。
2)相反,如果边连接两个强连通分量,并且边与两个分量之间的现有路径的方向相反,则将生成一个新的强连通分量,从而增加分量的数量。
我认为第二点是不正确的。
假设我们有两个强连通分量C 和C'
a) 如果它们之间不存在边或边C->C'并且新边连接为C->C' 那么什么都不会发生。
b) 如果它们之间存在边 C->C' ,并且新边连接为C'->C ,则 C' 将合并到 C,将强连通分量的数量减少 1,因为每个顶点都可以相互访问。
如果我错了,请纠正我。