并查集的定义
并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。
——百度百科
并查集，顾名思义，支持以下两种操作操作：
- 并(Union)：把两个不相交的集合合并为一个集合。
- 查(Find)：查询两个元素是否在同一个集合中。
并查集的实现
并查集往往用树来存，若使用\(f\)数组表示每个节点的父节点，则\(f_i\)表示第\(i\)个节点的父节点，初始\(f_i=i\)，初始节点即认自己为父亲，
那么我们就可以得到这样的一颗树：
查询
初始化时每个节点的根节点就是它自己。
int f[N];
int find(int x){
if(f[x]==x)return x;
return find(f[x]);
}
但这样会有一个问题：当数据很大时，树的深度会很高，所以我们需要压缩路径。
我们可以在查询的过程中，让每个点认自己的祖先为父亲，那么就可以大大缩小深度。(即路径压缩)
优化代码如下：
int f[N];
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
这样树就会变成
合并
假如要合并两棵树：
和
先路径压缩并找到组先（分别为 \(1\) 和 \(7\)）
和
再将 \(7\) 并到 \(1\) 下：
所以得出结论：
当要合并两个子集是，可以让被合并的子集的祖先任另一个子集的祖先为父亲
代码如下：
int a,b;
cin>>a>>b;
int fs=find(a),fs2=find(b);
if(fs!=fs2)fa[fs]=fs2;
例题
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int fa[10010]={0},ans;
int find(int x){
if(x!=fa[x])fa[x]=find(fa[x]);
return fa[x];
}
int s,n,m,a,b;
signed main(){
//freopen("bicj.out","w",stdout);
while(1){
cin>>n;
bool t1[10001]={0};
if(n==0)break;
cin>>m;
if(m==0){
cout<<n-1<<endl;
continue;
}
ans=n;
for(int i=1;i<=n+3;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
t1[a]=t1[b]=1;
int fs=find(a),fs2=find(b);
fa[fs]=fs2;
}
int t[1500]={0},ans=0;
for(int i=1;i<=n;i++){
t[find(i)]++;
//cout<<find(i)<<" ";
}
//cout<<endl;
for(int i=1;i<=n;i++){
if(t[i])ans++;
}
cout<<ans-1<<endl;
}
return 0;
}