# Union Find

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

1. 判断在不在同一个集合中

• find 操作

2. 关于集合合并

• 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) {
WeightedQuickUnionPathCompressionUF uf = new WeightedQuickUnionPathCompressionUF(n);
while (!StdIn.isEmpty()) {
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