CF1559 - D2. Mocha and Diana (Hard Version)

D2. Mocha and Diana (Hard Version)

题意

给出两个森林，两个森林中的点编号都是从 $1\ldots n$，第一个森林中有 $m_1$ 条边，第二个森林中有 $m_2$ 条边，可以进行连边操作，每次对两个森林中的顶点 $(u, v)$ 进行连边，并要求每次连边之后两个都仍是森林（即不会出现环，注：一棵树也是森林），求最多能连多少条边，并输出每次连的边。

数据范围：$N\leqslant 10^5$

思路

引理：最多连的边数一定是 $\min(n-m_1-1,n-m_2-1)$。

证明：

不妨令 $m_1\leqslant m_2$。

• 首先，最多连的边数一定不会超过 $n-m_1-1$，因为当森林变为一棵树的时候，边数最多为 $n-1$，现有 $m_1$ 条边，则最多不能加超过 $n-m_1-1$ 条边。

• 其次，如果连的边数小于 $n-m_1-1$ 则说明，第一个森林中至少还有两棵树，如果当前已经不能连边，则说明，在这两棵树中分别任取两个顶点，在第二个森林中，都是在一棵树中的，如果对于任意两个节点都有这个性质，那么第二个森林就已经是一棵树了，这与 $m_2\leqslant m_1$ 矛盾，因为不可能第一个森林还没变为一棵树，第二个森林已经提前变为一棵树。

综上，原命题得证。

QED

---

也就是说：达成最大连边数，当且仅当，两个森林中至少有一个森林只有一棵树。

下面考虑如何求出每次连的边，按照下述步骤进行：

• 先将1号顶点能连的边，全部连上。

• 然后在第一个森林中，除了包含1号顶点的树中都任意取一个顶点出来，第二个森林也从除了包含1号顶点的树中都任取一个顶点出来，然后顺次连边即可。

下面给出一个例子：

步骤2中，在森林1中不包含1号顶点的树只有3号节点，在森林2中不包含1号顶点的树只有2号顶点，最后直接将2和3连接即可。

下面给出这样操作的正确性证明：

证明：

令森林1中的连通点集合（也就是一棵树中的点）记为 $S_i$，森林2中的连通点集合记为 $T_i$，不妨假设顶点1属于 $S_1,T_1$。

通过步骤一我们可以发现，在森林1中，如果存在 $S_1$ 和 $S_2$，则说明1号顶点不能和 $S_2$ 中任意的一个顶点进行连边，这说明在森林2中，顶点1和 $S_2$ 中的点一定在同一棵树中，也就是 $S_2\subseteq T_1$。

那么接下来，如果取 $\forall u\in S_i, (i\geqslant 2)$，则有 $u\in T_1$，故 $u\not\in T_j, (j\geqslant 2)$。

于是我们可以取 $\forall v\in T_j,(j\geqslant 2)$，连接 $(u, v)$，这样就能将 $S_1, S_i$ 和 $T_1, T_j$ 同时合并。

也就是说下面这样的操作具有正确性（即不会连成环）。

设森林1中一共有 $n$ 棵树，森林2中一共有 $m$ 棵树，设 $\min = \min(n, m)$。

那么通过连接：

$$\begin{aligned} &(u_2, v_2),\quad(u_2\in S_2, v_2\in T_2)\\ &(u_3, v_3),\quad(u_3\in S_3, v_3\in T_3)\\ &\cdots\\ &(u_i, v_i),\quad(u_i\in S_i, v_i\in T_i)\\ &\cdots\\ &(u_{\min}, v_{\min}),\quad(u_{\min}\in S_{\min}, v_{\min}\in T_{\min})\\ \end{aligned}$$

就一定会将其中一个森林最终转换为只有一棵树，由引理得知，达到题目要求。

QED

---

用并查集维护集合，总复杂度 $O(NlogN)$，其实并查集复杂度远小于 $O(logN)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 1e5 + 10;
int fa[2][N];
int getfa(int i, int x) {
	if (fa[i][x] == x) return x;
	return fa[i][x] = getfa(i, fa[i][x]);
}
void join(int i, int x, int y) {
	fa[i][getfa(i, x)] = getfa(i, y);
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m[2];
	cin >> n >> m[0] >> m[1];
	for (int i = 1; i <= n; i++) fa[0][i] = fa[1][i] = i;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < m[i]; j++) {
			int u, v;
			cin >> u >> v;
			join(i, u, v);
		}
	}
	vp ans;
	for (int i = 2; i <= n; i++) {
		if (getfa(0, 1) != getfa(0, i) && getfa(1, 1) != getfa(1, i)) {
			ans.pb({1, i});
			join(0, 1, i);
			join(1, 1, i);
		}
	}
	for (int i = 2, j = 2; i <= n; i++) {
		if (getfa(0, 1) != getfa(0, i)) {
			for (; j <= n; j++) {
				if (getfa(1, 1) != getfa(1, j)) {
					ans.pb({i, j});
					join(0, i, j);
					join(1, i, j);
					break;
				}
			}
		}
	}
	cout << ans.size() << '\n';
	for (auto i : ans) cout << i.first << ' ' << i.second << '\n';
	return 0;
}

参考

CSDN-RunningBeef-D2. Mocha and Diana (Hard Version)