并查集专题 杭电OJ1232 灵巧求并和路径压缩

本文主要是介绍并查集专题 杭电OJ1232 灵巧求并和路径压缩，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

并查集也叫不相交集合，可以描述把一个集合通过等价关系（满足自反性、对称性和传递性的关系）划分为若干个等价类这一过程。并查集只有两个操作：find 和 union。find 返回一个元素所属的等价类，union 合并两个元素所在的等价类。

本文以杭电OJ1232题为例，说明并查集的实现和两种优化（按秩合并和路径压缩）（题目链接）。

竞赛向的板子

const int N=10010;
int father[N];
int Find(int x){if(x!=father[x]) father[x]=Find(father[x]);return father[x];
}
void Union(int a,int b){father[Find(a)]=Find(b);
}
void Init(){for(int i=0;i<N;++i) father[i]=i;
}

低效但直观的一种实现

第一种实现，数组的每个元素储存它所在等价类的名字。 find 例程只要返回元素的值就好了；而 union 例程则遍历数组进行修改。

对于连续的 N 次 find 操作或 union 操作，这种实现需要的时间分别为 O(N) 和 O(N^2)

#include<bits/stdc++.h>
using namespace std;
int bjset[1010];
int bjset_find(int x){return bjset[x];
}
void bjset_union(int x, int y,int n){int classx = bjset_find(x);int classy = bjset_find(y);if (classx != classy) {for (int i = 1; i <= n; ++i

这篇关于并查集专题 杭电OJ1232 灵巧求并和路径压缩的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---