并查集

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的 合并 及 查询 问题。 它支持两种操作：

• 查找（Find）：确定某个元素处于哪个子集；
• 合并（Union）：将两个子集合并成一个集合。

查找

int fa[MAXN];  // 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
int find(int x) {
  // 寻找x的祖先
  if (fa[x] == x)  // 如果x是祖先则返回
    return x;
  else
    return find(fa[x]);  // 如果不是则x的爸爸问x的爷爷
}

路径压缩

把在路径上的每个节点都直接连接到根上，这就是路径压缩。

int find(int x) {
  if (x != fa[x])  // x不是自身的父亲，即x不是该集合的代表
    fa[x] = find(fa[x]);  // 查找x的祖先直到找到代表,于是顺手路径压缩
  return fa[x];
}

合并

把一个祖先合并到别人祖先下，成为儿子。

void unionSet(int x, int y) {
  // x 与 y 所在家族合并
  x = find(x);
  y = find(y);
  fa[x] = y;  // 把 x 的祖先变成 y 的祖先的儿子
}

//时间复杂度O(n) ，递归程序
const int N=10010;
int s[N];
void init_set(){//初始化 
    for(int i=1;i<=N;i++) s[i]=i;
}

int find_set(int x){//查找 
    return x=s[x]?x:find_set(s[x]);//递归查找 
}

void union_set(int x,int y){
    x=find_set(s[x]);
    y=find_set(s[y]);
    if(x!=y) s[x]=s[y];
} 

按树的高度合并

int s[N],height[N];
//时间复杂度O(logn) 
void init_set(){//初始化 
    for(int i=1;i<=N;i++) 
    s[i]=i,height[i]=0;
}

int find_set(int x){//查找 
    int r=x;
    while(s[r]!=r) r=s[r];
    int i=x,j;
    while(i!=r){
        j=s[i];
        s[i]=r;
        i=j;
    }
    return r;
}

void union_set(int x,int y){
    x=find_set(s[x]);
    y=find_set(s[y]);
    if(height[x]==height[y]){
        height[x]=height[x]+1;//合并树的高度加一 
        s[y]=x;
    }
    else{
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;//矮树合并在高树上，高度不变 
    }
} 

题目

洛谷P3367

考察并查集的两个基本操作。这题要关流。

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define sc(n) scanf("%lld",&n)
#define SC(n,m) scanf("%lld%lld",&n,&m)
#define pr(n) printf("%lld\n",n);
int f[100010];

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

int main(){
	ios
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			f[find(x)]=find(y);
		}
		else{
			puts(find(x)==find(y)? "Y" : "N");
		}
	}
	return 0;
}

HDU1213

#include<bits/stdc++.h>
using namespace std;

const int N=100010;

int s[N],height[N];
//时间复杂度O(logn) 
void init_set(){//初始化 
    for(int i=1;i<=N;i++) s[i]=i;
}

int find_set(int x){//查找 
    return x==s[x]?x:find_set(s[x]);//递归查找 
}

void union_set(int x,int y){
    x=find_set(s[x]);
    y=find_set(s[y]);
    if(x!=y) s[x]=s[y];
} 

int main(){
    int t,n,m,x,y;
    cin>>t;
    while(t--){
        cin>>n>>m;
        init_set();
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            union_set(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(s[i]==i) ans++;
        }
        cout<<ans<<endl;
    }
    return 0; 
}