Solution:
First, it is obvious that we will use "Disjoint-set data structure" to determine whether two points are in the same tree.
We can get a conclusion that the number of edges that can be added in the end is $\max(n-1-m1,n-1-m2)$. In other words: at least one of the two forests will eventually merge into one tree.
Suppose there are two trees in Mocha's forest, denoted by ma and mb respectively. Then all points in ma and all points in mb are not linked. Diana avoids adding an edge between ma and mb. So in Diana's forest, all points in ma and all points in mb must be in one tree.
Since in the end, one of the forests must be combined into a tree. This means that if we choose any point as the root, eventually all nodes on one side will be below this root.
So we first try to connect each point to this root. For each point, we mark (x,y) to indicate that the point is on the tree numbered x in Mocha, and on the tree numbered y in Diana.
And for each point, there are 4 possibilities:
1. (1,1), that is, this point is on the tree where the root is located for both Mocha and Diana;
2. (1,?);
3. (?,1);
4. (?,?).
if and only if it is the 4th case, this point can be directly connected to the root.
For the first case, this point is actually already connected to the root. Therefore, no need to worry about this.
So what is left is only the cases of (1,?) and (?,1).
For a certain point, it is obviously impossible to satisfy both cases (1,?) and (?,1) at the same time. Therefore, we find any point from each of these two conditions, and these two points must can be linked.
So we can continue to repeat this process until one of these two cases no longer have any nodes. At this time, the forest corresponding to this condition has merged into one tree.
Code:
Java
C++
