并查集是一种以集合的合并和查询的一种结构。
并查集:
- 将两个集合合并
- 询问两个元素是否在一个集合当中
基本原理:
每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点储存它的父节点,p[x]
表示x
的父节点。
问题1: 如何判断树根: if(p[x] == x)
问题2: 如何求x的集合编号: while(p[x] != x) x = p[x];
问题3: 如何合并两个集合: px 是x的集合编号, py 是y的集合编号。 p[p[x]] = py
题目: 并查集
来源: https://www.acwing.com/problem/content/838/
一共有n个数,编号是1~n,最开始每个数各自在一个集合中。
现在要进行m个操作,操作共有两种:
“M a b”,将编号为a和b的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
“Q a b”,询问编号为a和b的两个数是否在同一个集合中;
输入格式
第一行输入整数n和m。
接下来m行,每行包含一个操作指令,指令为“M a b”或“Q a b”中的一种。
输出格式
对于每个询问指令”Q a b”,都要输出一个结果,如果a和b在同一集合内,则输出“Yes”,否则输出“No”。
每个结果占一行。
数据范围
$1≤n,m≤10^5$
输入样例:
1 2 3 4 5 6
| 4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4
|
输出样例:
c++ 代码实现
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
| #include <iostream>
using namespace std; const int N = 100010; int p[N], n, m;
int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }
int main() { cin >> n >> m; for(int i = 1; i <= n; i++) p[i] = i;
while(m--) { char op[2]; int a, b; scanf("%s%d%d", op, &a, &b);
if (op[0] == 'M') p[find(a)] = find(b); else { if (find(a) == find(b)) puts("Yes"); else puts("No"); } }
return 0; }
|
题目: 连通块中点的数量
来源: https://www.acwing.com/problem/content/839/
给定一个包含n个点(编号为1~n)的无向图,初始时图中没有边。
现在要进行m个操作,操作共有三种:
- “C a b”,在点a和点b之间连一条边,a和b可能相等;
- “Q1 a b”,询问点a和点b是否在同一个连通块中,a和b可能相等;
- “Q2 a”,询问点a所在连通块中点的数量;
输入格式
第一行输入整数n和m。
接下来m行,每行包含一个操作指令,指令为“C a b”,“Q1 a b”或“Q2 a”中的一种。
输出格式
对于每个询问指令”Q1 a b”,如果a和b在同一个连通块中,则输出“Yes”,否则输出“No”。
对于每个询问指令“Q2 a”,输出一个整数表示点a所在连通块中点的数量
每个结果占一行。
数据范围
$1≤n,m≤10^5$
输入样例:
1 2 3 4 5 6
| 5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5
|
输出样例:
思路:
只需要在上一题的基础上添加一个size数组,用来维护根节点所在集合的元素个数就好。只需要维护根节点元素的个数就行。
C++实现
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
| #include <iostream>
using namespace std; const int N = 100010; int p[N], cnt[N], n, m;
int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }
int main() { cin >> n >> m; for(int i = 1; i <= n; i++) { p[i] = i; cnt[i] = 1; }
while(m--) { char op[5]; int a, b; scanf("%s", op); if (op[0] == 'C') { scanf("%d%d", &a, &b); if (find(a) == find(b)) continue; cnt[find(b)] += cnt[find(a)]; p[find(a)] = find(b); } else if (op[1] == '1'){ scanf("%d%d", &a, &b); if (find(a) == find(b)) puts("Yes"); else puts("No"); } else { scanf("%d", &a); printf("%d\n", cnt[find(a)]); } }
return 0; }
|
题目: 食物链
来源: https://www.acwing.com/problem/content/242/
动物王国中有三类动物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和K句话,输出假话的总数。
输入格式
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
输出格式
只有一个整数,表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
输入样例:
1 2 3 4 5 6 7 8
| 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
|
输出样例:
思路:
这里使用并查集来做,利用集合的合并来表示两个物种间是否在之前出现过。这里开一个格外数组,用来维护某点到根节点的距离。这个距离取模为3就表示第几代。形成一个环状结构,如果取模相等就表示两个物种是同一个物种,如果取模不等切相差为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
| #include <iostream>
using namespace std;
const int N = 50010; int p[N], d[N], n, m;
int find(int x) { if( p[x] != x ) { int t = find(p[x]); d[x] += d[p[x]]; p[x] = t; } return p[x]; }
int main() { scanf("%d%d", &n, &m); for(int i = 1; i<= n; i++) p[i] = i;
int res = 0; while( m-- ) { int op, x, y; scanf("%d%d%d", &op, &x, &y);
if (x > n || y > n) res++; else{ int px = find(x), py = find(y); if (op == 1) { if (px == py && (d[x] - d[y]) % 3) res++; else if (px != py ) { p[px] = py; d[px] = d[y] - d[x]; } } else { if(px == py && (d[x] - d[y] - 1) % 3) res++; else if(px != py) { p[px] = py; d[px] = d[y] - d[x] + 1; } } } }
cout << res << endl; return 0; }
|