定义
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。就是元素可以为集合的集合
实现
可以用pre[1000]数组来存储这个并查集
初始化： 每个节点初始状态都是一个自身的集合，即pre[i]=i;
void InitSet(int n){
for(int i=0;i<n;i++){
pre[i]=i;
}
}
查找根节点及路径压缩
查找根节点就是返回集合的代表元素所在，路径压缩就是把所有非根节点的父节点修改为根节点，这样，就变成了仅有根节点和叶子节点的树，仅有两层
int pre[1000];
int Find(int x)
{
//以下实现查找根节点
int r=x;
while(r!=pre[r])
r=pre[r];
//以下代码用来实现路径压缩
int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
也可以下面的,这个包含了查找和路径压缩，fa就是pre
int Find(int x) {
return fa[x] == x ? x : fa[x] = Find(fa[x]) ;
}
集合合并
查找两个集合的根节点并合二为一
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}
模板
python3
class UnionFind:
def __init__(self):
self.parent = {}
def union(self, a: int, b: int):
ra = self.find(a)
rb = self.find(b)
self.parent[ra] = rb
def find(self, a: int) -> int:
if a not in self.parent:
self.parent[a] = a
if self.parent[a] == a:
return a
ra = self.find(self.parent[a])
self.parent[a] = ra
return ra
def is_connected(self, a, b):
return self.find(a) == self.find(b)
python3 带每个集合数量
class UnionFind:
def __init__(self):
self.parent = {}
self.size = {}
def union(self, a: int, b: int):
ra = self.find(a)
rb = self.find(b)
if ra == rb: return
self.parent[ra] = rb
self.size[rb] += self.size[ra]
def find(self, a: int) -> int:
if a not in self.parent:
self.parent[a] = a
self.size[a] = 1
if self.parent[a] == a:
return a
ra = self.find(self.parent[a])
self.parent[a] = ra
return ra
def is_connected(self, a, b):
return self.find(a) == self.find(b)
相关题目
java实现
import java.io.BufferedInputStream;
import java.util.ArrayDeque;
import java.util.Scanner;
public class Solution {
static final int maxn=100000;
static int[] f=new int[maxn];
static int find(int x){
return x==f[x]?x:(f[x]=find(f[x]));
}
static void union(int x,int y){
int fa=find(x);
int fb=find(y);
if(fa!=fb){
f[fa]=fb;
}
}
static void init(){
for(int i=0;i<f.length;i++){
f[i]=i;
}
}
public static void main(String[] args){
Scanner in=new Scanner(new BufferedInputStream(System.in));
init();
while (in.hasNext()){
int a=in.nextInt();
int b=in.nextInt();
union(a,b);
System.out.println(find(a));
}
// System.out.println(f[3]);
// System.out.println(find(3));
}
}
应用
求连通图的数量 用一个新的数组t[1000]，并fill(t,t+1000,0); 然后遍历所有节点，t(Find(x))=1,数组t中为1的数量就是连通子图的数量
求修路问题？ 就是连通图数量减一呀
Kruskal最小生成树用的好像就是这个呀！！
例题
#include<iostream>
using namespace std;
int pre[1050];
bool t[1050]; //t 用于标记独立块的根结点
int Find(int x)
{
int r=x;
while(r!=pre[r])
r=pre[r];
int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void mix(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}
int main()
{
int N,M,a,b,i,j,ans;
while(scanf("%d%d",&N,&M)&&N)
{
for(i=1;i<=N;i++) //初始化
pre[i]=i;
for(i=1;i<=M;i++) //吸收并整理数据
{
scanf("%d%d",&a,&b);
mix(a,b);
}
memset(t,0,sizeof(t));
for(i=1;i<=N;i++) //标记根结点
{
t[Find(i)]=1;
}
for(ans=0,i=1;i<=N;i++)
if(t[i])
ans++;
printf("%d\n",ans-1);
}
return 0;
}//dellaserss
冗余连接
题目描述：有一系列的边连成的图，找出一条边，移除它之后该图能够成为一棵树。
public int[] findRedundantConnection(int[][] edges) {
int N = edges.length;
UF uf = new UF(N);
for (int[] e : edges) {
int u = e[0], v = e[1];
if (uf.connect(u, v)) {
return e;
}
uf.union(u, v);
}
return new int[]{-1, -1};
}
private class UF {
private int[] id;
UF(int N) {
id = new int[N + 1];
for (int i = 0; i < id.length; i++) {
id[i] = i;
}
}
void union(int u, int v) {
int uID = find(u);
int vID = find(v);
if (uID == vID) {
return;
}
for (int i = 0; i < id.length; i++) {
if (id[i] == uID) {
id[i] = vID;
}
}
}
int find(int p) {
return id[p];
}
boolean connect(int u, int v) {
return find(u) == find(v);
}
}
加权并查集
必看：https://leetcode-cn.com/problems/evaluate-division/solution/399-chu-fa-qiu-zhi-nan-du-zhong-deng-286-w45d/
区别： 除了维护 parent 这样的节点指向关系，我们还需要维护节点的权重，一个简单的想法是使用另外一个哈希表 weight 存储节点的权重关系。比如 weight[a] = 1 表示 a 到其父节点的权重是 1。
除法的并查集
class Solution:
root = {}
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
self.root = {}
for i in range(len(equations)):
ei = equations[i]
vi = values[i]
self.union(ei[0], ei[1], vi)
print(self.root)
res = []
for iq in queries:
a, b = iq[0], iq[1]
if a in self.root and b in self.root:
a_ra, ra = self.find(a)
b_rb, rb = self.find(b)
if ra != rb:
res.append(-1.0)
else:
res.append(a_ra / b_rb)
else:
res.append(-1.0)
return res
def union(self, a, b, a_b):
if a not in self.root:
self.root[a] = [1.0, a]
if b not in self.root:
self.root[b] = [1.0, b]
a_ra, ra = self.find(a)
b_rb, rb = self.find(b)
self.root[ra] = [b_rb * a_b / a_ra, rb]
def find(self, i):
tmp = i
assert i in self.root # i invalid
path, rate, base = [], [], 1.0
while self.root[i][1] != i:
path.append(i)
rate.append(self.root[i][0])
base *= self.root[i][0]
i = self.root[i][1]
ra = i
for i in range(len(path)):
ip = path[i]
self.root[ip][1] = ra
self.root[ip][0] = base
base = base / rate[i]
return self.root[tmp]