ACM_JLINE.

并查集课件

并查集
字数统计: 2.8k阅读时长: 14 min
2019/04/16 Share

并查集

(当然又是备课)

程序自动分析

原题链接：NOI 2015

题目大意：

给你两个值，告诉你相等或者不相等，问最后是否有矛盾的。

题解：

并查集裸题
由于数字范围比较大，所以简单离散化一下
直接贴代码

Code block

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
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

const int N = 200005;
int fa[N], x, y, z, b[N];
int n, t, m, cnt;
struct node{
	int x, y, f; 
}a[N];

int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

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

void Init(){
	scanf("%d", &n);
	cnt = 0;
	m = 0;
	for(int i = 1; i <= n; i++){
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].f);
		b[cnt++] = a[i].x;
		b[cnt++] = a[i].y;
	}
	
	sort(b, b + cnt);
	m = unique(b, b + cnt) - b;        //去重
	
	for(int i = 0; i <= m; i++){  //离散化过后这个地方要小心！！！不能 i = 1
		fa[i] = i;
	}
}

int main(){
	scanf("%d", &t);
	while(t--){
		int f = 0;
		
		Init();
		
		for(int i = 1; i <= n; i++){
			int x = lower_bound(b, b + m, a[i].x) - b;
			int y = lower_bound(b, b + m, a[i].y) - b;
			if(a[i].f == 1){
				merge(x, y);
			}
		}
		
		for(int i = 1; i <= n; i++){
			int x = lower_bound(b, b + m, a[i].x) - b;
			int y = lower_bound(b, b + m, a[i].y) - b;
			if(a[i].f == 0){
				int fx = find(x), fy = find(y);
				if(fx == fy){
					f = 1;
					printf("NO\n");
					break;
				}
			}
		}
		if(f == 0) printf("YES\n");
	} 
	return 0;
}

“扩展域” 与 “边带权” 的并查集

分数调查

原题链接：hiho 1515

题目大意：

告诉你多对两个人之间的分数差关系，求任意两个人的分数差

题解：

带权并查集

Code block

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

const int N = 100005;
int d[N], fa[N], x, y, z, n, m, t;

int find(int x){
	if(fa[x] == x) return x;
	int root = find(fa[x]);
	d[x] += d[fa[x]];  //边权求和
	return fa[x] = root;
}

void merge(int x, int y, int w){
	int fx = find(x), fy = find(y);
	if(fx == fy) return ;
	
	fa[fx] = fy;
	
	d[fx] = w - d[x] + d[y]; 
}

int main(){
	scanf("%d%d%d", &n, &m, &t);
	
	for(int i = 1; i <= n; i++){
		fa[i] = i;
		d[i] = 0;
	}
	
	for(int i = 1; i <= m; i++){
		scanf("%d%d%d", &x, &y, &z);
		merge(x, y, z);
	}
	
	for(int i = 1; i <= t; i++){
		scanf("%d%d", &x, &y);
		if(find(x) != find(y)){
			printf("-1\n");
			continue;
		}
		printf("%d\n", d[x] - d[y]);
	} 
	return 0;
}

银河传说英雄

原题链接：NOI 2002

题目大意：

有一个划分成N列的星际战场，各列依次编号为1，2，… ，N。有N艘战舰, 也依次编号为1，2，…，N，其中第 i 号战舰处于第 i 列
有M条指令，每条指令格式为以下两种之一：

1．M i j，表示让第号战舰所在列的全部战舰保持原有顺序，接在弟j号战舰所在列的尾部。
2．C i j，表示询问第号战舰与第号战舰当前是否处于同一列中，如果在同列中，它们之间间隔了多少艘战舰。
M ≤ 3000 M ≤ 5e5。

题解：

带权并查集
用size[] 记录每个树根上集合大小，merge时更新一下。

Code block

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

const int N = 30005;
int fa[N];
int d[N], size[N];
int t, x, y;
char ch;
int find(int x){
	if(x == fa[x]) return x;
	int root = find(fa[x]);
	d[x] += d[fa[x]];
	return fa[x] = root;
}

void merge(int x, int y){
	int fx = find(x);
	int fy = find(y);
	fa[fx] = fy;
	d[fx] = size[fy];
	size[fy] += size[fx];
}

int main(){
	for(int i = 1; i < N; i++){
		fa[i] = i;
		d[i] = 0;
		size[i] = 1;
	}
	scanf("%d", &t);
	while(t--){
		cin >> ch >> x >> y;
		if(ch == 'M') {
			int fx = find(x), fy = find(y);
			merge(x, y);
		}
		else if(ch == 'C'){
			int fx = find(x), fy = find(y);
			if(fx != fy) {
				printf("-1\n");
			}
			else printf("%d\n", abs(d[x] - d[y]) - 1);
		}
	}
	return 0;
}

Parity game

原题链接：POJ 1733

题目大意：

输入 n 表示有一个长度为 n 的 0, 1 字符串, m 表示接下来有 m 行输入, 接下来的 m 行输入中 x, y, even 表示第 x 到第 y 个字符中间 1 的个数为偶数个, x, y, odd 表示第 x 到第 y 个字符中间 1 的个数为奇数个, 若 m 句话中第 k + 1 是第一次与前面的话矛盾,输出 k

题解：

奇偶，对对对就是异或

“边带权”

Code block

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 20005;
struct node{
	int l, r, f;
}q[N];
int fa[N], a[N], d[N], x, y, n, t;
char ch[5];
int cnt;

void init(){
	scanf("%d", &n);
	scanf("%d", &t);
	for(int i = 1; i <= t; i++){
		scanf("%d%d%s", &q[i].l, &q[i].r, ch);
		q[i].f = (ch[0] == 'o' ? 1 : 0);
		a[cnt++] = q[i].l - 1;
		a[cnt++] = q[i].r;
	}
	sort(a, a + cnt);
	n = unique(a, a + cnt) - a;
	
	for(int i = 1; i <= n; i++){
		fa[i] = i;
		d[i] = 0;
	}
}

int find(int x){
	if(x == fa[x]) return x;
	int root = find(fa[x]);
	d[x] ^= d[fa[x]];
	return fa[x] = root;
}

int main(){
	init();
	for(int i = 1; i <= t; i++){
		int x = lower_bound(a, a + n, q[i].l - 1) - a;
		int y = lower_bound(a, a + n, q[i].r) - a;
		
		int fx = find(x), fy = find(y);
		
		if(fx == fy){
			if((d[x] ^ d[y]) != q[i].f){
				printf("%d\n", i -1);
				return 0;
			}
		}
		else{
			fa[fx] = fy;
			d[fx] = d[x] ^ d[y] ^ q[i].f;
		}
	}
	printf("%d\n", t);
	return 0; 
}

“扩展域” (个人感觉这题这样解法比较容易写)

Code block

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 20005;
struct node{
	int l, r, f;
}q[N];
int fa[2 * N], a[N], x, y, n, t;
char ch[5];
int cnt;

void init(){
	scanf("%d", &n);
	scanf("%d", &t);
	for(int i = 1; i <= t; i++){
		scanf("%d%d%s", &q[i].l, &q[i].r, ch);
		q[i].f = (ch[0] == 'o' ? 1 : 0);
		a[cnt++] = q[i].l - 1;
		a[cnt++] = q[i].r;
	}
	sort(a, a + cnt);
	n = unique(a, a + cnt) - a;
	
	for(int i = 1; i <= 2 * n; i++){
		fa[i] = i;
	}
}

int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main(){
	init();
	for(int i = 1; i <= t; i++){
		int x = lower_bound(a, a + n, q[i].l - 1) - a;
		int y = lower_bound(a, a + n, q[i].r) - a;
		
		int x_odd = x, x_even = x + n;
		int y_odd = y, y_even = y + n;
		
		if(q[i].f == 0){
			if(find(x_odd) == find(y_even)){
				printf("%d\n", i - 1);
				return 0;
			}
			else{
				fa[find(x_odd)] = find(y_odd);
				fa[find(x_even)] = find(y_even);
			}
		}
		else{
			if(find(x_odd) == find(y_odd)){
				printf("%d\n", i - 1);
				return 0;
			}
			else{
				fa[find(x_odd)] = find(y_even);
				fa[find(x_even)] = find(y_odd);
			}
		}
	}
	printf("%d\n", t);
	return 0; 
}

食物链

原题链接：POJ 1182

题目大意：

动物王国中有三类动物A, B, C，这三类动物的食物链构成了有趣的环形。A 吃 B， B 吃 C，C 吃 A。
现有 N 个动物，以 1 － N 编号。每个动物都是 A, B, C 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中 X 或 Y 比 N 大，就是假话；
3） 当前的话表示 X 吃 X ，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

题解：

每个动物拆成三个节点，同类域 捕食域 天敌域
矛盾情况：
“x 与 y 是同类”

  1. x 捕食域 与 y 同类域 在同一集合，说明 x 吃 y。
  2. x 同类域 与 y 捕食域 在同一集合，说明 y 吃 x。

“x 吃 y”

  1. x 同类域 与 y 同类域 在同一集合，说明 x 与 y 是同类。
  2. x 同类域 与 y 捕食域 在同一集合，说明 y 吃 x。

Code block

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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 300005; 
int x, y, z, n, t, d, cnt;
int fa[N];

int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main(){
	scanf("%d%d", &n, &t);
	for(int i = 1; i <= 3 * n; i++){
		fa[i] = i;
	}
	for(int i = 1; i <= t; i++){
		scanf("%d%d%d", &d, &x, &y);
		
		if(x > n || y > n){
			cnt++;
			continue;
		}
		int x1 = x, x2 = x + n, x3 = x + 2 * n;
		int y1 = y, y2 = y + n, y3 = y + 2 * n;
		if(d == 1){
			if(find(x2) == find(y1) || find(x1) == find(y2)){
				cnt++;
				continue;
			}
			else{
				fa[find(x1)] = find(y1);
				fa[find(x2)] = find(y2);
				fa[find(x3)] = find(y3);
			}
		}
		else{
			if(find(x1) == find(y1) || find(x1) == find(y2) || x == y){
				cnt++;
				continue;
			}
			else{
				fa[find(x1)] = find(y3);
				fa[find(x2)] = find(y1);
				fa[find(x3)] = find(y2);
			}
		}
	}
	printf("%d\n", cnt);
	return 0;
}

Rochambeau

原题链接：POJ 2912

题目大意：

石头剪刀布游戏 只有一个人是可以变化的，其余的只会出一种手势，问能否找出那个人。

题解：

暴力枚举每个人是那个特殊人的情况
先去掉与当前枚举有关的信息 看看是否会出现矛盾
不知道为什么搞了一下扩展域，差点调不出来。
这题还是比较好玩的！！！

Code block

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
102
103
104
105
106
107
108
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 10005;
int fa[N], x, y, n, m;
int a[N], b[N]; 
char ch[N];

int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

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

void solve(){
	int num = 0;
	int h = 0;
	int ans = 0;
	for(int i = 0; i < n; i++){  //枚举裁判 
	
		for(int j = 0; j <= 3 * n; j++){ //初始化 
			fa[j] = j;
		}
		
		int flag = 0;
		
		for(int j = 1; j <= m; j++){
			if(a[j] == i || b[j] == i) continue;
			
			int x1 = a[j], x2 = n + x1, x3 = 2 * n + x1;
			int y1 = b[j], y2 = n + y1, y3 = 2 * n + y1;
			if(ch[j] == '='){
				if(find(x1) == find(y2) || find(x1) == find(y3) 
				|| find(x2) == find(y1) || find(x2) == find(y3)
				|| find(x3) == find(y1) || find(x3) == find(y2))
				{
					flag = 1;h = max(h, j);
					break;
				}
				else{
					merge(x1, y1);
					merge(x2, y2);
					merge(x3, y3);
				}
			}
			else if(ch[j] == '<'){
				if(find(x1) == find(y1) || find(x1) == find(y2) 
				|| find(x2) == find(y2) || find(x2) == find(y3)
				|| find(x3) == find(y1) || find(x3) == find(y3))
				{
					flag = 1;h = max(h, j);
					break;	
				}
				else {
					merge(x1, y3);
					merge(x2, y1);
					merge(x3, y2);
				}
			}
			else if(ch[j] == '>'){
				if(find(x1) == find(y1) || find(x1) == find(y3) 
				|| find(x2) == find(y1) || find(x2) == find(y2)
				|| find(x3) == find(y2) || find(x3) == find(y3))
				{
					flag = 1;h = max(h, j);
					break;
				}
				else {
					merge(x1, y2);
					merge(x2, y3);
					merge(x3, y1);
				}
			}
			
		}
		
		if(flag == 0){ //没矛盾 
			num++;
			ans = i; 
		}
	}
	if(num == 0){
		printf("Impossible\n");
	}
	else if(num == 1){
		printf("Player %d can be determined to be the judge after %d lines\n", ans, h);
	}
	else{
		printf("Can not determine\n");
	}
	
}
int main(){
	while(~scanf("%d%d", &n, &m)){
		for(int i = 1; i <= m; i++){
			cin >> a[i] >> ch[i] >> b[i];
		}
		solve();
	}
	return 0;
}

原文作者：CHEN

原文链接：http://yourself.com/2019/04/16/并查集/

发表日期：April 16th 2019, 9:00:22 pm

更新日期：April 16th 2019, 9:00:08 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 并查集
    1. 1.1. 程序自动分析
    2. 1.2. 原题链接：NOI 2015
      1. 1.2.1. 题目大意：
      2. 1.2.2. 题解：
      3. 1.2.3. Code block
  2. 2. “扩展域” 与 “边带权” 的并查集
    1. 2.1. 分数调查
    2. 2.2. 原题链接：hiho 1515
      1. 2.2.1. 题目大意：
      2. 2.2.2. 题解：
      3. 2.2.3. Code block
    3. 2.3. 银河传说英雄
    4. 2.4. 原题链接：NOI 2002
      1. 2.4.1. 题目大意：
      2. 2.4.2. 题解：
      3. 2.4.3. Code block
    5. 2.5. Parity game
    6. 2.6. 原题链接：POJ 1733
      1. 2.6.1. 题目大意：
      2. 2.6.2. 题解：
      3. 2.6.3. Code block
      4. 2.6.4. Code block
    7. 2.7. 食物链
    8. 2.8. 原题链接：POJ 1182
      1. 2.8.1. 题目大意：
      2. 2.8.2. 题解：
      3. 2.8.3. Code block
    9. 2.9. Rochambeau
    10. 2.10. 原题链接：POJ 2912
      1. 2.10.1. 题目大意：
      2. 2.10.2. 题解：
      3. 2.10.3. Code block
Total : 28
2019
Invalid date
2019
Invalid date
Invalid date
2019
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
Invalid date
差分约束 KMP 二分 最短路 二分图 素数筛 LCA 树上差分 set维护 ICPC ccpc Hello CF 倍增 归并 随笔 贪心 map DP 树链剖分 树状数组 DFS CSP 贪心 并查集 dfs序 set 扫描线
ACM 最短路