并查集
2021-01-25 本文已影响0人
siliconx
1. 概念
并查集主要用于解决一些元素分组的问题，管理一系列不相交的集合，并支持两种操作：
• 查询（Find）：查询两个元素是否在同一个集合中；
• 合并（Union）：把两个不相交的集合合并为一个集合。
并查集一般用于集合、无向图，一般情况下不适用于有向图（但也有例外Leetcode 685. 冗余连接II）。
2. 标准模板：
Java:
class DSU {
private int components; // 连通分量的个数
private int[] parent; // 根节点
public DSU(int n) {
components = n;
parent = new int[n];
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void merge(int a, int b) {
int ap = find(a);
int bp = find(b);
if (ap != bp) {
--components;
parent[bp] = ap;
}
}
public int getComponents() {
return components;
}
}
C++:
class DSU {
private:
int components; // 记录连通分量的个数
vector<int> parent; // 记录每个节点的根节点
public:
DSU(int n) {
parent.resize(n);
components = n;
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int x) {
// 查找x的根节点
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void merge(int x, int y) {
// 合并两个连通分量
int fx = find(x);
int fy = find(y);
if (fx != fy) {
--components;
parent[fx] = fy;
}
}
int getComponents() {
return components;
}
};
Python:
class DSU(object):
def __init__(self, n):
self.n = n
self.parent = [i for i in range(n)]
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def merge(self, a, b):
ap = self.find(a)
bp = self.find(b)
if ap != bp:
self.parent[bp] = ap
