作用

1.将两个集合合并

2.询问两个元素是否在一个集合中

用并查集可以用近乎 $O(1)$ 的时间复杂度完成两个操作

原理

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

除了根节点之外，p[x]都不等于 $x$ ，因此判断树根可以用 if(p[x]==x)

求 $x$ 的集合编号：while(p[x]!=x)x=p[x]

合并集合：再两个集合中加一条边，相当于左面的集合是右边的集合的儿子。假设 $px$ 是 $x$ 的集合编号， $py$ 是 $y$ 的集合编号。p[x]=y

找根节点路径压缩优化：如果 $x$ 找到的根节点，那么所有集合人都指向根节点

存储集合里元素的数量cnt[find(y)]+=cnt[find(x)]

并查集应用

一.朴素并查集

1.返回 $x$ 的祖宗节点（前面有详细解析）

int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

p[]数组存储每个点的祖宗节点

2.初始化

for(int i=1;i<=n;i++)p[i]=i初始化，假定节点编号是1~n

3.朴素合并的并查集

合并 $a$ 和 $b$ 所在的两个集合

p[find(a)]=b

二.维护连通块的并查集

1.size数组含义

size[]表示祖宗节点所在集合中点的数量

2.初始化

for(int i=1;i<=n;i++){
    size[i]=1;
}

因为初始的时候每个集合只有一棵树，所以都为 $1$

3.合并集合

size[find(b)]+=size[find(a)];
p[find(a)=find(b)]

三.基本操作

1.判断 $a$ 和 $b$ 是否在一个集合中

if(find(a)==find(b))是
else 不是

2.输出 $a$ 所在的集合中元素数量

cout<<cnt[find(a)]