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

C++