Union Find
并查集: 一种用来解决集合查询/合并的数据结构 支持O(1) find / O(1) union操作
A very good source for Union Find:
Princeton CS Algorithms 4th Edition: https://algs4.cs.princeton.edu/15uf/
Union Find: 一种用于支持集合快速合并和查找操作的数据结构
O(1)合并两个集合- Union
O(1)查询元素所属集合- Find
基本数据结构是：使用哈希表或者数组来存储每个节点的父亲节点
并查集可以干什么? What Union Find Can Do?
判断在不在同一个集合中
find 操作
关于集合合并
union 操作
并查集应用场景总结：
1.合并两个集合
2.查询某个元素所在集合
3.判断两个元素是否在同一个集合
4.获得某个集合的元素个数
5.统计当前集合个数
并查集的操作 Union Find - Operation
查询 Find (递归? 非递归?)
模板代码
HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();
int find(int x) {
int parent = x;
while (parent ! = father.get(parent)) {
parent = father.get(parent);
}
return parent;
}合并 Union
老大哥之间合并 跟小弟没关系
HashMap<Integer, Integer> father = new HashMap<Integer. Integer>();
void union(int x, int y) {
int fa_x = find(x);
int fa_y = find(y);
if (fa_x != fa_y) {
father.put(fa_x, fa_y);
}
}并查集完整模板 Union Find Template
HashMap Based
class UnionFind {
UnionFind() {}
HashMap<Integer, Integer> father = new HashMap<Integer. Integer>();
int find(int x) {
int parent = x;
while (parent ! = father.get(parent)) {
parent = father.get(parent);
}
return parent;
}
void union(int x, int y) {
int fa_x = find(x);
int fa_y = find(y);
if (fa_x != fa_y) {
father.put(fa_x, fa_y);
}
}
}Array Based
Weighted quick-union with path compression
https://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html
public class WeightedQuickUnionPathCompressionUF {
private int[] parent; // parent[i] = parent of i
private int[] size; // size[i] = number of sites in tree rooted at i
// Note: not necessarily correct if i is not a root node
private int count; // number of components
/**
* Initializes an empty union–find data structure with {@code n} sites
* {@code 0} through {@code n-1}. Each site is initially in its own
* component.
*
* @param n the number of sites
* @throws IllegalArgumentException if {@code n < 0}
*/
public WeightedQuickUnionPathCompressionUF(int n) {
count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/**
* Returns the number of components.
*
* @return the number of components (between {@code 1} and {@code n})
*/
public int count() {
return count;
}
/**
* Returns the component identifier for the component containing site {@code p}.
*
* @param p the integer representing one site
* @return the component identifier for the component containing site {@code p}
* @throws IllegalArgumentException unless {@code 0 <= p < n}
*/
public int find(int p) {
validate(p);
int root = p;
while (root != parent[root])
root = parent[root];
while (p != root) {
int newp = parent[p];
parent[p] = root;
p = newp;
}
return root;
}
/**
* Returns true if the the two sites are in the same component.
*
* @param p the integer representing one site
* @param q the integer representing the other site
* @return {@code true} if the two sites {@code p} and {@code q} are in the same component;
* {@code false} otherwise
* @throws IllegalArgumentException unless
* both {@code 0 <= p < n} and {@code 0 <= q < n}
*/
public boolean connected(int p, int q) {
return find(p) == find(q);
}
// validate that p is a valid index
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
/**
* Merges the component containing site {@code p} with the
* the component containing site {@code q}.
*
* @param p the integer representing one site
* @param q the integer representing the other site
* @throws IllegalArgumentException unless
* both {@code 0 <= p < n} and {@code 0 <= q < n}
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// make smaller root point to larger one
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
/**
* Reads in a sequence of pairs of integers (between 0 and n-1) from standard input,
* where each integer represents some site;
* if the sites are in different components, merge the two components
* and print the pair to standard output.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
int n = StdIn.readInt();
WeightedQuickUnionPathCompressionUF uf = new WeightedQuickUnionPathCompressionUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}Another Weighted + Path Compression - Simpler Version
public class UnionFind {
int[] parent;
int[] rank;
int cnt;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
rank = new int[n];
cnt = n;
}
public boolean union(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) return false;
cnt--;
if (rank[pa] < rank[pb]) {
parent[pa] = pb;
} else {
parent[pb] = pa;
if (rank[pa] == rank[pb]) rank[pa]++;
}
return true;
}
public int find(int a) {
while (a != parent[a]) {
parent[a] = parent[parent[a]];
a = parent[a];
}
return a;
}
}Last updated