练习：22.5-1 CLRS
如果一个新的图的强连通分量的数量如何改变
添加了边缘？
某处 http://student.csuci.edu/~douglas.holmes253/Assignment6.html给出的答案是如果添加新边缘，则可能会发生以下两种情况之一。
1) 如果新边连接的两个顶点属于强连通分量，则强连通分量的数量将保持不变。
2) 相反，如果边连接两个强连通分量，并且该边与两个分量之间现有路径的方向相反，则将生成一个新的强连通分量，从而增加分量的数量。
我认为第二点是不正确的。假设我们有两个强连接的组件C and C'
a) 如果无边或有边C->C'它们之间存在并且新的边连接为C->C'那么什么都不会发生。
b) 如果边缘C->C'它们之间存在并且新的边连接为C'->C那么 C' 将合并到 C，将强连通分量的数量减少 1，因为每个顶点都可以相互到达。
如果我错了，请纠正我。
你说得完全正确。您引用的答案在其描述中是错误的：添加边只会减少强连接组件的数量。一旦添加了所有可能的边，就只剩下一个强连接的组件 - 整个图。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
