有向グラフに 1 つの有向辺を追加すると、弱
連結要素の数を減らすことができますが、最大で何要素分減るのでしょうか?
強連結成分の数はどうでしょうか?
私の解決策は正しいですか？
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