Codeforces Round #738 Mocha and Diana (hard&easy) 题解 (Java/C++)

题解

首先,显而易见,我们会使用并查集来判断两个点是不是在同一个树里。

我们可以得到一个结论,最终能添加的边数为$\max(n-1-m1,n-1-m2)$。也就是说:两个森林中至少有一个森林最终会合并成为一棵树。
假设Mocha的森林中有两棵树,分别记为ma,mb。那么ma中的所有点和mb中的所有点都没有链接。此时Diana为了不让ma和mb可以链接,那么在Diana这边,ma中的所有点和mb中的所有点都必须在一棵树中。

既然最终,必然有一边会合成一棵树。这就意味着如果我们选任意一个点作为根,最终会有一边的所有节点都在这个根的下面。

于是我们首先尝试将每个点与这个根相连。对于每个点,我们记(x,y)表示这个点在Mocha里是在编号为x的树上,在Diana里是在编号为y的树上。而对于每个点,无非是有4种可能:1. (1,1),即这个点对于Mocha和Diana都在根所在的树上;2. (1,?);3. (?,1);4. (?,?)。
其中只有是第4种情况时,这个点可以直接与根相连。
而对于第1种情况,这个点其实已经连接到根上。因此也不需要考虑。
所以剩下的就只是(1,?)和(?,1)的情况。

对于某一个点来说,显然他不可能同时满足(1,?)和(?,1)两种条件。因此,我们从这两个条件各找任意一个点出来,这两个点一定可以链接。
于是我们可以不断重复这个过程,直到这两个条件中的某一个条件不再有点符合。此时这个条件所对应的森林已经合并成了一棵树。

代码

Java

Submission #126433835 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #126434178 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论