【模板】并查集

发布于 Feb 14, 2020 更新于 Jan 8, 2021

 

【模板】并查集——查询合并

适用场景

当程序涉及大量不交集“元素分类”,“类别合并”,“类别查询”时可以考虑使用并查集
但注意,不支持集合的分离与删除

并查集的原理

并查集通过维护一棵树实现。每个子节点都指向一个父节点,直到指向到“祖先”,每个节点对应着的“祖先”有且只有一个,而不同的“祖先”则对应着不同的集合。在查询时,只需迭代找到祖先;在添加新元素时,只需要把元素指向对应集合的一个父节点;在合并时,只需把一者的祖先指向另一者的祖先。

模板代码

int f[maxn];
int find(int i) {	//递归寻找i的祖先,并进行路径压缩
  if (i != f[i])
    f[i] = find(f[i]);
  return f[i];
}
void uni(int i, int j) {	//将y集合并入x的祖先旗下
	int x = find(i), y = find(j);
	if (x == y) return;
	f[y] = x;
}

 

标签

Noam Chi

An Innovative Quant Developer. 2018 VEX World Final THINK Award🏆