在有向图中添加单个有向边可以减少弱
连接组件的数量,但最多减少多少个组件?那么
强连接组件的数量呢?
我的解决方案正确吗?
Suppose a graph G' use one vertex to represent
a strongly/weakly connected component (SCC/WCC) of a directed graph G
=> G' is a DAG.
If the directed edge we add makes a cycle in the graph
then all the vertices in that cycle are in a SCC
so we reduce it to one vertex.
The number of SCCs reduced is n-1,
where n is the number of vertices in the cycle