3

在有向图中添加单个有向边可以减少弱
连接组件的数量,但最多减少多少个组件?那么
强连接组件的数量呢?

我的解决方案正确吗?

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
4

0 回答 0