• 周二. 11 月 12th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CF 1559D2. Mocha and Diana

admin

11 月 28, 2021

题目描述

有`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)$ 。

发表回复