首先我们先考虑Eazy Version。容易发现，在\(A,B\)两个森林中一定有一个是一棵树。这个结论说明：
-
选边顺序没影响
-
能选就选
因此我们枚举\(n^2\)条边，用并查集判断连通性即可
最终复杂度\(O(n^2 \alpha(n))\)或\(O(n^2logn)\)
然后我们考虑Hard Version怎么做。我们发现上面的做法我们多判断了很多条边。例如我们连接了\((x,y)\)，则我们还会继续判断\((x,z)\)，其中\(z\)和\(x\)在同一个连通块里。这是很不优的。因此我们考虑优化
首先我们先枚举连接所有能连接的边\((1,u)\)，此时点分成了三类：
-
\(1\)在\(A\)图中和\(u\)联通，在\(B\)图中和\(u\)联通
-
\(1\)在\(A\)图中和\(u\)联通，在\(B\)图中和\(u\)不联通
-
\(1\)在\(A\)图中和\(u\)不联通，在\(B\)图中和\(u\)联通
我们把第二类节点和第三类节点分别划分在集合\(L\)和\(R\)中，容易发现\(L \cap R = \emptyset\)，并且在\(L\)和\(R\)内的所有节点都是可匹配的。因为如果在\(L\)中有\(x\)和\(R\)中\(y\)不匹配，则说明在\(A\)图或\(B\)图中\(x,y\)在同一连通块内，因此\(x,y\)应该在同一集合中，假设不成立。
因此我们接下来的策略就是在\(L\)和\(R\)中随便选两个点\(x,y\)，连边，把\(L\)和\(R\)中联通的点删去，并重复此操作直到\(L\)和\(R\)之一为空
最终复杂度\(O(n \alpha(n))\)或\(O(n \log n)\)