摘要
Title: 836. 合并集合
Tag: 并查集
Memory Limit: 64 MB
Time Limit: 1000 ms

836. 合并集合

题意

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 a 和 b 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
思路

并查集
- 将两个集合合并
- 询问两个元素是否在一个集合当中
近乎 $O(1)$ 完成这两个操作

基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点，fa[x] 表示x的父节点

问题：
- 如何判断树根 if fa[x] == x
- 如何求x的集合编号 while fa[x] != x: x = fa[x]
  - 意思就是，只要x不是树根，就可以一直往上走，直到x满足树根的性质
- 如何合并两个集合
  - 假设a是x的集合编号，b是y的集合编号，fa[a] = b即可，即将x集合插到y集合去
  - 还是相当于连了一条有向边，即a指向b
优化：
- 路径压缩
  - 某个点找到根节点的过程中，使每个路径上的点都指向根节点
- 按秩合并 不常用

代码

'''
Author: NEFU AB-IN
Date: 2022-03-01 15:51:43
FilePath: \ACM\Acwing\836.py
LastEditTime: 2022-03-01 16:04:30
'''
N = int(1e5 + 10)
fa = [i for i in range(N)]


def find(x):
    if fa[x] != x:
        fa[x] = find(fa[x])
    return fa[x]


n, m = map(int, input().split())

for i in range(m):
    op, a, b = input().split()
    a, b = int(a), int(b)
    if op == 'M':
        fa[find(a)] = find(b)
    else:
        if find(a) == find(b):
            print("Yes")
        else:
            print("No")

836. 合并集合

题意

思路

代码