前言
摘自 Leetcode
并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。
- Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- Union：将两个子集合并成同一个集合。
摘自 Wiki
在计算机科学中，不相交集数据结构（Disjoint Sets），也称为并查集或合并查找集(merge–find set)，是存储不相交（非重叠）集合的数据结构。同样地，它将一个集合的一个分区存储为不相交的子集。它提供添加新集、合并集合（用联合替换它们）和查找集合成员的操作。最后一个操作可以有效地找出任何两个元素是否在相同或不同的集合中。
虽然有几种方法可以实现不相交集的数据结构，但在实际操作中，它们通常与一个称为不相交集林的特定实现来识别。这是一种特殊类型的森林，它执行联合，并在几乎恒定的平摊时间内发现。要在具有n个节点的不相交集森林上执行m个加法、并集或查找操作，需要总时间O(mα(n))，其中α(n)是增长非常缓慢的逆阿克曼函数。不相交集的森林并不能保证在每个操作的基础上实现这种性能。单个联合和查找操作可能花费的时间超过α(n)时间，但每个操作都会导致不相交集的森林进行调整，使连续操作更快。不相交集森林是渐近最优的和实际有效的。
并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。
一、java 实现
1.1 组成
并查集类主要由一个整型数组 parent[] 和两个方法 find()、union() 构成。
- 数组 parent[] 记录了每个点的根节点是谁
- 方法 find(x) 用于查找指定节点 x 属于哪个集合，
- 方法 union(x, y) 用于合并两个节点 x 和 y , 连通到一个集合。至于是将x合并至y，还是将y合并至x，可以根据实际情况判断，下面实现默认将x合并至y。
1.2 代码
public class UnionFind {
private int [] parent;
public UnionFind(int n) {
parent = new int[n];
// 初始化，默认节点的根节点为自己
for(int i = 0; i < n; i++){
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}
二、Leetcode 实战
2.1 省份数量
https://leetcode.cn/problems/number-of-provinces/
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
这题是最标准的并查集题目了，只要审好题，使用并查集工具类就能轻松完成
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
UnionFind union = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1) {
union.union(i, j);
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (union.find(i) == i) ans++;
}
return ans;
}
class UnionFind {
private int [] parent;
public UnionFind(int n) {
parent = new int[n];
for(int i = 0; i < n; i++){
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]);
}
void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot != yRoot) {
parent[xRoot] = yRoot;
}
}
}
}
2.2 除法求值
https://leetcode.cn/problems/evaluate-division/
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
这题用并查集做的话，就要用到带权重的并查集，就是不仅需要存储属于哪个集合，还要将和根之间的权重存储下来。
需要改造下之前的UnionFind类，初始化权重值，还有需要在find 和 union 两个方法中加入权重的存储判断。
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Integer> map = new HashMap<>();
int count = 0;
UnionFind unionFind = new UnionFind(equations.size() * 2);
double [] ans = new double[queries.size()];
for (int i = 0; i < equations.size(); i++) {
List<String> strings = equations.get(i);
String key1 = strings.get(0);
String key2 = strings.get(1);
if (!map.containsKey(key1)) {
map.put(key1, count++);
}
if (!map.containsKey(key2)) {
map.put(key2, count++);
}
Integer t1 = map.get(key1);
Integer t2 = map.get(key2);
unionFind.union(t1, t2, values[i]);
}
Set<Integer> set = new HashSet<>();
for (int i = 0; i < queries.size(); i++) {
List<String> strings = queries.get(i);
String key1 = strings.get(0);
String key2 = strings.get(1);
Integer t1 = map.getOrDefault(key1, -1);
Integer t2 = map.getOrDefault(key2, -1);
ans[i] = (t1 == -1 || t2 == -1) ? -1.0 : unionFind.findWeight(t1, t2);
}
return ans;
}
class UnionFind {
private int [] parent;
private double [] weight;
public UnionFind(int n) {
parent = new int[n];
weight = new double[n];
for(int i = 0; i < n; i++){
parent[i] = i;
}
Arrays.fill(weight, 1.0d);
}
int find(int x) {
if (x != parent[x]) {
int origin = parent[x];
parent[x] = find(parent[x]);
weight[x] *= weight[origin];
}
return parent[x];
}
void union(int x, int y, double w) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
weight[x] = w * weight[y] / weight[rootY];
}
}
double findWeight(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return weight[x] / weight[y];
} else {
return -1.0d;
}
}
}
2.3 冗余连接
https://leetcode.cn/problems/redundant-connection/
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
这题也是典型的并查集题目，开始时理解题意有点困难，等明白后代码就很简单
在一棵树中，边的数量比节点的数量少 1。如果一棵树有 n 个节点，则这棵树有 n−1 条边。这道题中的图在树的基础上多了一条附加的边，因此边的数量也是 n
用边的两个节点来构成并查集，只要两个点的根节点不相等，那就可以将这两个点连通。如果相等，两个节点都可以到根，再加上这条边，就构成了环，这条边就是可以删去的。
至于题目中说有多个答案，返回最后出现的边，实际操作中可以发现，用上述方法删去的边总是最后出现的边，这是因为题目中已经说明只有1个环，就是多出的那条边构成环，而前面在构造并查集时已经连通了各个点，当连成环时必是最后一条可以删除的边
public int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
UnionFind unionFind = new UnionFind(n);
for (int [] edge: edges) {
if (unionFind.find(edge[0] - 1) != unionFind.find(edge[1] - 1)) {
unionFind.union(edge[0] - 1, edge[1] - 1);
} else {
return edge;
}
}
return null;
}
class UnionFind {
private int [] parent;
public UnionFind(int n) {
parent = new int[n];
// 初始化，默认节点的根节点为自己
for(int i = 0; i < n; i++){
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}
2.4 冗余连接II
https://leetcode.cn/problems/redundant-connection-ii/
在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
这题和上题类似，不过是有向图。不仅需要考虑有环，还需要考虑无环下冲突的情况：一个点有两个父节点。
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
UnionFind unionFind = new UnionFind(n);
int conflict = -1;
int cycle = -1;
for (int i = 0; i < n; i++) {
int a = edges[i][0];
int b = edges[i][1];//此时a指向b b要认a为父亲
if (unionFind.parent[b] != b){//冲突 b的父亲早就不是自己了
conflict = i;//找到了后一条冲突边
} else {
if (unionFind.find(a) == unionFind.find(b)){//有循环，即能够查找到相同的祖先
cycle = i;//记录出现循环的边
} else
unionFind.parent[b] = a;//都不是的情况就让b的父节点指向a
}
}
if (conflict < 0) {//没有冲突边 纯循环，那么最后导致出现循环的边就是答案
return new int[]{edges[cycle][0], edges[cycle][1]};
} else if (cycle >= 0) {//有冲突边，也有循环边,那么除了冲突的的另一个父亲分支有问题
int[] c = edges[conflict];
return new int[]{unionFind.parent[c[1]], c[1]};
} else {//只有冲突边
int[] c = edges[conflict];
return new int[]{edges[conflict][0], edges[conflict][1]};
}
}
class UnionFind {
private int[] parent;
private int[] inDegree;
public UnionFind(int n) {
parent = new int[n];
inDegree = new int[n];
// 初始化，默认节点的根节点为自己
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
inDegree[y]++;
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}