基本操作
每一个元素初始时都是独立的一个集合
for(int i = 1; i
递归查找的过程，直到找到一个元素值等于其集合的值即其根节点的集
int find_set(int x){
return x == f[x] ? x : find_set(f[x]);
}
合并两个集合，通过查找操作找到其集的值，若不相等则修改其中一个使两个集的值指向同一个根节点的0值
void union_set(int x, int y){
x = find_set(x);
y = find_set(y);
if(x != y) s[x] = s[y];
}
即统计一个根节点的数量，直接阐述较为抽象故引例
题目大意
偷偷BB，就是求有多少个
#include
#include
#include
using namespace std;
const int N = 1010;
int f[N];
int T, n, m, x, y;
// 初始化
void init_set(){
for(int i = 1; i
优化原理：找到两个根节点，根据其高度，总使高度较小的集合合并到较大的集合中去，最终减少树的高度
int height[maxn + 1]; // 初始化时用height来定义元素i的高度，并在初始化时修改
void init_set(){
for(int i = 1; i
优化原理：这个优化的原理很简单，如果每次找父节点都要按照原路径找一遍显然太鸡儿蠢了。
在递归返回时，沿路把路径上的点都直接指向父节点，下次就可以在O（1）的时间内得到结果
上代码！！！
// 递归版本
int find_set(int x){
if(x != f[x]) f[x] = find_set(f[x]); // 路径压缩
return f[x];
}
// 非递归版本
int find_set(x){
int t = x;
while(f[t] != t) t = f[t]; // 此时t为根节点
int i = x, j;
while(i != t){
j = f[i]; // 用变量j记录i的父节点
f[i] = t; // 把路径上的元素的集改为根节点
i = j; // 新的i是原来i的父节点，继续改下一个点
}
return t;
}
参考《算法竞赛——入门到进阶》–罗勇军 第五章 5.1并查集
后续习题有时间会发布，敬请期待;o((>ω< ))o# 并查集Original: https://www.cnblogs.com/hhc-blog/p/15388300.html
Author: hcのBlog
Title: 并查集
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584626/
转载文章受原作者版权保护。转载请注明原作者出处！