1. 并查集
并查集解决的是不相交集合的合并及查询问题。并查集的本质是一种树形数据结构，每个集合对应一棵树。当需要执行“合并两个元素所在集合”类似操作时，则可能会用到并查集。
在并查集中，每个节点指向其父节点，而根节点的父节点为其自身，而根节点本身就可以代表整个集合。即，对于一个节点，如果通过递归调用父节点，最终可以追溯到某个根节点，那么该节点就属于这个根节点所代表的集合。
在执行合并两个元素所在集合（即合并两个节点所在的树）操作时，并查集会首先检查两个节点所在树的根节点是否是同一个；如果是的话，则说明不需要合并；反之，则使其中一个根节点成为另一个根节点的子节点。
通俗地讲，并查集就相当于若干“原始部落”，每个节点都是部落的成员，而根节点就是部落的“首领”。子节点的查询就相当于成员找到上级，上级又找到上级的上级，最后追溯到部落的首领。而集合的合并就相当于部落的兼并，两个部落合并成一个，首领只剩一个，另一个则俯首称臣（成为另一个根的子节点）。
1.1 并查集的特点
并查集有以下特点：
- 包含一个或若干树状结构，每棵树代表一个集合，每个节点代表集合中的一个元素；
- 树中节点只知道自己的父节点；
- 根节点的父节点为其自身；
- 可以执行合并操作，将两个节点所在的树合并成一棵树；合并之后，一棵树的根节点成为另一棵树根节点的子节点。
1.2 并查集的一般形式
/**
* 并查集
*
* @param <T> 节点类型
*/
public class UnionFind<T> {
protected int size;
protected final Map<T, T> parent = new HashMap<>();
/**
* @param orig 原始数据集
*/
public UnionFind(T[] orig) {
for (T t : orig) {
parent.put(t, t); // 每个节点作为一个根节点
}
size = orig.length;
}
/**
* 合并两个节点所在的树
*/
public void union(T node1, T node2) {
T root1 = find(node1);
T root2 = find(node2);
if (root1 != root2) {
parent.put(root2, root1); // 使树2成为树1子树
size--;
}
}
/**
* 查询节点node所在树的根节点
*/
public T find(T node) {
if (!parent.containsKey(node)) return null;
while (parent.get(node) != node) node = parent.get(node);
return node;
}
public int size() {
return size;
}
}
2. 例题
2.1 例1 城市道路系统问题
输入一个整型数组
int[] cities，每个元素代表一个城市；
输入若干对整数int[][] roads，每对整数表示对应的两个城市之间修建有道路。
如果城市之间能通过道路到达，那么称这些城市处于同一个道路系统。
问：总共有多少个道路系统？
假设城市数组为{1,2,3,4,5,6,7,8,9}，
道路为{1,2}, {3,4}, {4,5}, {6,8}, {1,6}, {9,5}。
并查集的思路：
首先把每个原始数据各自分割成一个集合：{1}{2}{3}{4}{5}{6}{7}{8}{9}；
连通道路{1,2}（即合并1、2所在集合）：{1,2}{3}{4}{5}{6}{7}{8}{9}；
连通道路{3,4}（即合并3、4所在集合）：{1,2}{3,4}{5}{6}{7}{8}{9}；
连通道路{4,5}（即合并4、5所在集合）：{1,2}{3,4,5}{6}{7}{8}{9}；
连通道路{6,8}（即合并6、8所在集合）：{1,2}{3,4,5}{6,8}{7}{9}；
连通道路{1,6}（即合并1、6所在集合）：{1,2,6,8}{3,4,5}{7}{9}；
连通道路{9,5}（即合并9、5所在集合）：{1,2,6,8}{3,4,5,9}{7}；
因为最后合并成了3个集合，故一共有3个道路系统。
例题代码实现：
public int countRoadSystem(int[] cities, int[][] roads) {
UnionFind<Integer> uf = new UnionFind<Integer>(cities);
for (int[] road : roads) uf.union(road[0], road[1]);
return uf.size();
}
其中并查集的代码为第一节中的一般形式。
2.2 例2 Leetcode 947. 移除最多的同行或同列石头
题目Leetcode 947. 移除最多的同行或同列石头
题解Leetcode 947. 移除最多的同行或同列石头
题目：
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,1] 同行。
- 移除石头 [2,1] ，因为它和 [0,1] 同列。
- 移除石头 [1,2] ，因为它和 [1,0] 同行。
- 移除石头 [1,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,0] 同行。
- 移除石头 [2,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
示例 3：
输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。
提示：
- 1 <= stones.length <= 1000
- 0 <= xi, yi <= 104
- 不会有两块石头放在同一个坐标点上
题解
容易得到：
- 对于两个石子A和B，如果二者同行/列，那么A和B属于同一集合；
- 对于石子A、B、C，如果A、B属于同一集合，且B、C属于同一集合，那么A、C属于同一集合；
- 对于一个大小为
n的石子集合，可以移除n - 1枚石子。
遍历数组stones，对于每一个石子{x, y}，天然都属于两个集合：第x行、第y列。于是，将第x行与第y列的石子合并成一个新的集合即可。
public int removeStones(int[][] stones) {
UnionFind<Integer> uf = new UnionFind<>();
for (int[] stone : stones) {
int x = stone[0];
int y = stone[1];
uf.union(x, -y - 1); // 合并"第x行"与"第y列"，其中用负数代替第y列
}
return stones.length - uf.size();
}
