题目描述
有`A`、`B`两个各含有 $n$ 个点的森林,可以往两边都加入相同的边,问能最多加多少条且输出这些边。
数据范围
$n le 10^5$
题解
很巧妙的贪心题。
首先我们想最终状态,如果A是森林,那B一定是一棵树,因为A中的每两棵树之间的点在B间都是连通的,反之亦然。
所以我们可以在其中一个森林里考虑能不能让一个点连通到其他点。
考虑1这个点,我们在两张图中先加入和1都不连通的边。然后将在A中不连通在B中连通的点放在一个栈SA内,在B中不连通在A中连通的点放在另一个栈SB内。
然后每次从SA中弹出点直到该点在A中与1不连通,SB也一样,接着将这两个点相连即可。
这样有一边的栈最后肯定会空,也就意味着形成一棵树了,那就是加入了最多的边了。
效率: $O(n)$ 。