本文从WordPress迁移而来, 查看全部WordPress迁移文章
连通分量
给一个无向图,删除两个点,使得新图的连通分量数最大
做法是枚举一个点,删掉它,然后在剩下的图中求割点
计算删除每个割点,会使每个图分裂为多少部分,枚举割点
(其实也可以不用枚举,只要找到一个割点可以使图分裂成最多部分,那就行了,但枚举的话,时间也差不多)
删除一个点后图的连通分量数为CNT,删除一个割点能产生cnt[u]个连通分量,那么最后的连通分量是CNT + cut[u] - 1
注意,可能在找割点的过程中,找不到一个割点,那么只能随便删除一个点,那么图的连通分量就是 ANS = max(ANS,CNT)吗?
不一定的!因为一个无向图中,如果没有割点,删除一个点,图的连通分量数不一定保持不变,而是可能减少
1 | 例如 |
这种数据,删除点2,后得到1 3 4 5这些连通分量,CNT = 4,这些点中没有一个点是割点,那么任意删除一个点即可
但删除了一个点,连通分量数不变吗?不是的,而是-1
所以为了保证正确性,更新答案应该是
ANS = max(ANS,CNT-1);
1 |
|