theme: smartblue highlight: androidstudio
目录
1. 什么是并查集？
并查集是一种数据结构（数据结构相信大家都知道吧）
他能干什么呢？
并查集主要是用于处理一些不相交集合的合并问题
那么什么叫不相交集合呢？
举例：
比如一个城市有n个人，1号和3号是朋友，属于一个帮派的，5号和3号也是朋友，8号和9号是朋友，这个时候随便问你两个人，判断他们是否属于一个帮派（相互认识）
如果我们使用暴力的方式去判断的话，我们需要将互相认识的人保存在不同的帮派里面，然后对任意两个人查看是否处于同一个集合里面，最坏情况达到了0(n²)
这是非常不友好的，对于n = 1e6来说
那么，这个时候，我们就需要用到并查集这种数据结构了，可以使代码低于O(logn)
2. 并查集的基本操作
2.1 初始化
我们定义数组: , 代表是i元素所属的并查集（集合）
如下映射关系：
每个元素最开始的并查集（集合）都是自己
2.2 合并
现在，1和2是朋友关系，他们应该属于同一个集合：
1和3也是朋友：
相当于1，2，3其实都是朋友关系，他们理应属于同一个帮派（集合）
为了更简单处理这种合并关系，我们直接将集合2合并到集合3上，因为集合2里面包括了1和2
所以我们可以这样来表示这个集合数组：
大概意思就是：1的父亲是2，2的父亲是3，3的父亲是自己，这样就表示了一个集合（可以通过递归的形式，不断找自己的父亲，直到当前元素=自己的父亲，代表集合结束）
2.3 查找
不断递归查找自己的父亲元素，判断两个元素是否处于一个集合的条件：看两个的父亲元素是否相同
如果全都是一个父亲，那么查找的时候就非常耗时，需要进行O(N)次查找
后面会考虑使用路径压缩，来优化查找的时间复杂度
3. 基础代码
可以对照着这道题来：
import os
import sys
# 请在此输入您的代码
n, m = map(int, input().split())
s = list(range(n + 1)) # 初始化1-n
# 找自己的根节点（集合）
def find_root(x):
if x == s[x]: return x
return find_root(s[x])
# 合并a,b集合
def merge_set(a, b):
roota = find_root(a)
rootb = find_root(b)
s[roota] = rootb
for i in range(m):
op, x, y = map(int, input().split())
if op == 1:
merge_set(x, y)
else:
if find_root(x) == find_root(y):
print("YES")
else:
print("NO")
4. 合并优化
当然，上面的代码其实无法通过全部案例
我们可以思考一下，在我们进行查询合并的时候，我们需要不断递归查找根节点，这大概就是O(N)的时间复杂度了
所以我们需要路径压缩的优化：
路径压缩：其实就是简化查询根节点，我们可以每次进行搜索的时候，就将当前节点的父节点一直更改为父节点的父节点，最后的效果就是，每个集合元素的父节点就是根节点
通过路径压缩，我们可以O（1）的时间复杂度就可以求出集合的根节点啦
5. 最终代码
其实只需要更改find_root()代码的两行就可以了
import os
import sys
# 请在此输入您的代码
n, m = map(int, input().split())
s = list(range(n + 1)) # 初始化1-n
# 找自己的根节点（集合）
def find_root(x):
if x == s[x]: return x
s[x] = find_root(s[x]) # 路径压缩代码，不断将自己的父节点更改为父亲的父亲...
return s[x]
# 合并a,b集合
def merge_set(a, b):
roota = find_root(a)
rootb = find_root(b)
s[roota] = rootb
for i in range(m):
op, x, y = map(int, input().split())
if op == 1:
merge_set(x, y)
else:
if find_root(x) == find_root(y):
print("YES")
else:
print("NO")