【并查集】Codeforces Round 738 (Div. 2) D2. Mocha and Diana
2021-08-18 00:18:00 # ACM

题链

首先将两个图 $A,B$ 中的节点 $1$ 都视为根节点；
遍历剩下的每个节点 $[2,n]$：
  $1.$ 节点 $i$ 在两图中都与 $1$ 节点不相连，那么答案中加入 $<1,i>$；
  $2.$ 节点 $i$ 在两图中都与 $1$ 节点相连，那么这两点属于同一连通块，不需要管它；
  $3.$ 节点 $i$ 在一个图$(A)$中与 $1$ 节点相连，另一个图$(B)$中不相连，那么这个不相连的点也许可以和别的点连接，所以预先存入各自的栈$(B)$中；
接下来考虑两个栈$(A)(B)$中还剩下的点；
 将$(A)(B)$两栈栈顶元素$<u,v>$配对，这样配对后，$u,v$ 就会各自与自己图中的 $1$ 节点相连，原因就是 $A$ 栈中元素在 $B$ 图中是与 $1$ 相连的，$B$ 栈中元素在 $A$ 图中是与 $1$ 相连的；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <unordered_map>
#include <deque>
#include <stack>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define ll long long
#define MAXN 200000
#define mod 1000000007
#define MS 100005

int n,m1,m2;
int fa[3][MS];
int p[3][MS];
stack<int > sta[3];
int ac[MS][3], tot;

void init(){
	for (int i=1;i<=n;i++) fa[1][i] = fa[2][i] = i;
}

int find(int rt,int x){
	if (fa[rt][x] == x) return x;
	else return fa[rt][x] = find(rt,fa[rt][x]);
}

void merge(int rt,int x,int y){
	int fx = find(rt,x);
	int fy = find(rt,y);
	if (fx > fy) swap(fx,fy);
	fa[rt][fy] = fx;
}

void solve(){
	cin >> n >> m1 >> m2; init();
	for (int i=1;i<=m1;i++){
		int u,v;
		cin >> u >> v;
		merge(1,u,v);
	}
	for (int i=1;i<=m2;i++){
		int u,v;
		cin >> u >> v;
		merge(2,u,v);
	}
	
	for (int i=2;i<=n;i++){
		if (find(1,i) != 1 && find(2,i) != 1){
			tot++;
			ac[tot][1] = 1;
			ac[tot][2] = i;
			merge(1,1,i);
			merge(2,1,i);
		}
		else {
			if (find(1,i) != 1) sta[1].push(i);
			if (find(2,i) != 1) sta[2].push(i);
		}
	}
	while (!sta[1].empty() && !sta[2].empty()){
		int t1 = sta[1].top();
		if (find(1,t1) == 1 && find(2,t1) == 1){
			sta[1].pop();
			continue;
		}
		int t2 = sta[2].top(); 
		if (find(1,t2) == 1 && find(2,t2) == 1){
			sta[2].pop();
			continue;
		}
		merge(1,t1,t2); 
		merge(2,t1,t2);
		tot++;
		ac[tot][1] = t1; 
		ac[tot][2] = t2; 
	}
	
	cout << tot << "\n";
	for (int i=1;i<=tot;i++){
		cout << ac[i][1] << " " << ac[i][2] << "\n";
	}
	
}

int main(){
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
	//cin >> ce;
	while (ce--){
		solve();
	}
		
	return 0;	
}
Prev
2021-08-18 00:18:00 # ACM
Next