题目链接
This is the hard version of the problem. The only difference between the two versions is the constraint on
n
n
n. You can make hacks only if all versions of the problem are solved.
A forest is an undirected graph without cycles (not necessarily connected).
Mocha and Diana are friends in Zhijiang, both of them have a forest with nodes numbered from 1 1 1 to n n n, and they would like to add edges to their forests such that:
- After adding edges, both of their graphs are still forests.
- They add the same edges. That is, if an edge ( u , v ) (u, v) (u,v) is added to Mocha’s forest, then an edge ( u , v ) (u, v) (u,v) is added to Diana’s forest, and vice versa.
Mocha and Diana want to know the maximum number of edges they can add, and which edges to add.
Input
The first line contains three integers n n n, m 1 m_1 m1? and m 2 m_2 m2? ( 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105, 0 ≤ m 1 , m 2 < n 0 \le m_1, m_2 < n 0≤m1?,m2?<n) — the number of nodes and the number of initial edges in Mocha’s forest and Diana’s forest.
Each of the next m 1 m_1 m1? lines contains two integers u u u and v v v ( 1 ≤ u , v ≤ n 1 \le u, v \le n 1≤u,v≤n, u ≠ v u \neq v u?=v) — the edges in Mocha’s forest.
Each of the next m 2 m_2 m2? lines contains two integers u u u and v v v ( 1 ≤ u , v ≤ n 1 \le u, v \le n 1≤u,v≤n, u ≠ v u \neq v u?=v) — the edges in Diana’s forest.
Output
The first line contains only one integer h h h, the maximum number of edges Mocha and Diana can add.
Each of the next h h h lines contains two integers u u u and v v v ( 1 ≤ u , v ≤ n 1 \le u, v \le n 1≤u,v≤n, u ≠ v u \neq v u?=v) — the edge you add each time.
If there are multiple correct answers, you can print any one of them.
Examples
input
3 2 2
1 2
2 3
1 2
1 3
output
0
这道题貌似可以用各种随机乱搞等各种玄学卡过去，这里给出一个比较科学的的做法。
先说结论：最终边数较多的图一定连成了一棵树。
首先是加边问题，显然只要遇到满足条件的边就直接加上结果一定不会变差。因为假设加上这一条边会使得有两条及以上边加不上，因为加这条边影响的边只能是连接和这条边一样的连通分量的边，而这样的边要是加两条一定会出现环，这与条件矛盾，因此贪心的加即可。
然后考虑加边的策略，首先先按这种策略加边：枚举所有点，如果在两个图中均可以向节点
1
1
1 连边则直接连边。这样处理的结果是一定是下图所示类型：
其中一种颜色代表一类点集，相同颜色代表同一点集。
可以发现，此时可以继续加的边只能是蓝色和绿色点集之间的边，进而可以得出对于两图中不包含节点
1
1
1 的连通分量只能向外连至多一条边，并且不包含节点
1
1
1 的连通分量数量较少的图一定能连成一棵树。由此可以通过双指针
O
(
n
)
O(n)
O(n) 将剩余部分连完。并查集操作近似看做常数，总时间复杂度为
O
(
n
)
O(n)
O(n) 。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Union_Find {
int fa[N], rnk[N];
inline void init(int n) { iota(fa + 1, fa + 1 + n, 1); }
int get(int x) { return x == fa[x] ? x : (fa[x] = get(fa[x])); }
inline void merge(int x, int y) {
x = get(x), y = get(y);
if (x == y) return;
if (rnk[x] < rnk[y]) swap(x, y);
fa[y] = x;
if (rnk[x] == rnk[y]) rnk[x]++;
}
inline bool same(int x, int y) { return get(x) == get(y); }
} U1, U2;
int n, m1, m2, ans;
int main() {
scanf("%d%d%d", &n, &m1, &m2);
U1.init(n), U2.init(n);
for (int i = 1, x, y; i <= m1; i++)
scanf("%d%d", &x, &y), U1.merge(x, y);
for (int i = 1, x, y; i <= m2; i++)
scanf("%d%d", &x, &y), U2.merge(x, y);
printf("%d\n", ans = n - 1 - max(m1, m2));
for (int i = 2; i <= n; i++) {
if (U1.same(1, i) || U2.same(1, i)) continue;
printf("1 %d\n", i), ans--;
U1.merge(1, i), U2.merge(1, i);
}
for (int i = 2, j = 1; ans; i++) {
if (U1.same(1, i)) continue;
while (U2.same(1, j)) j++;
printf("%d %d\n", i, j), ans--;
U1.merge(1, i), U2.merge(1, j);
}
return 0;
}