algorithm - 添加 1 条边和数字的新图

Question

在准备课上ACM-Contest，我们的老师给了我们一个已解决问题的打印页。在一页上写着，2以下事实是真实的，但她不会说，why or what：

“通过向有向图添加新的 1 条边，关于该图的强连通分量的数量，其中有多少可能是正确的？

+) at most 1 unit is increased.

++) at most 1 unit is decreased.

+++) maybe not changed.

++++) maybe decreased by more than 2 units.

任何人都可以与我们的团队一起清楚地扩展它吗？

Answer 1

(+) 是错误的（在“最多增加”的宽泛解释下，即暗示没有减少）并且 (++) 是错误的并且 (++++) 是正确的，因为如果我们添加来自的反馈弧一条路径的一端到另一端，使其成为一个循环，然后我们从 n 个强分量变为 1。 (+++) 显然是正确的。

Before (4 strong components):
* --> * --> * --> *

After version A (1 strong component):
___________________
|                 |
v                 |
* --> * --> * --> *

After version B (4 strong components):
___________________
|                 |
|                 v
* --> * --> * --> *