# Union Find
**并查集**: 一种用来解决集合**查询**/**合并**的数据结构 支持O(1) find / O(1) union操作
A very good source for Union Find:
Princeton CS Algorithms 4th Edition:
**Union Find**: 一种用于支持集合**快速合并**和**查找**操作的**数据结构**
* O(1)合并两个集合- Union
* O(1)查询元素所属集合- Find
**基本数据结构**是：使用**哈希表**或者**数组**来存储每个**节点**的**父亲节点**
## 并查集可以干什么? What Union Find Can Do?
1. 判断在不在同一个集合中
* find 操作
2. 关于集合合并
* union 操作
**并查集应用场景总结：**
1.合并两个集合
2.查询某个元素所在集合
3.判断两个元素是否在同一个集合
4.获得某个集合的元素个数
5.统计当前集合个数
## 并查集的操作 Union Find - Operation
### 查询 Find (递归? 非递归?)
模板代码
```java
HashMap father = new HashMap();
int find(int x) {
int parent = x;
while (parent ! = father.get(parent)) {
parent = father.get(parent);
}
return parent;
}
```
### 合并 Union
老大哥之间合并\
跟小弟没关系
```java
HashMap father = new HashMap();
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
```java
class UnionFind {
UnionFind() {}
HashMap father = new HashMap();
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*
```java
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
```java
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;
}
}
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://aaronice.gitbook.io/lintcode/union_find.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.