1. 并查集

并查集解决的是不相交集合的合并及查询问题。并查集的本质是一种树形数据结构，每个集合对应一棵树。当需要执行“合并两个元素所在集合”类似操作时，则可能会用到并查集。

在并查集中，每个节点指向其父节点，而根节点的父节点为其自身，而根节点本身就可以代表整个集合。即，对于一个节点，如果通过递归调用父节点，最终可以追溯到某个根节点，那么该节点就属于这个根节点所代表的集合。

在执行合并两个元素所在集合（即合并两个节点所在的树）操作时，并查集会首先检查两个节点所在树的根节点是否是同一个；如果是的话，则说明不需要合并；反之，则使其中一个根节点成为另一个根节点的子节点。

通俗地讲，并查集就相当于若干“原始部落”，每个节点都是部落的成员，而根节点就是部落的“首领”。子节点的查询就相当于成员找到上级，上级又找到上级的上级，最后追溯到部落的首领。而集合的合并就相当于部落的兼并，两个部落合并成一个，首领只剩一个，另一个则俯首称臣（成为另一个根的子节点）。

1.1 并查集的特点

并查集有以下特点：

1. 包含一个或若干树状结构，每棵树代表一个集合，每个节点代表集合中的一个元素；
2. 树中节点只知道自己的父节点；
3. 根节点的父节点为其自身；
4. 可以执行合并操作，将两个节点所在的树合并成一棵树；合并之后，一棵树的根节点成为另一棵树根节点的子节点。

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 块石头的方法如下所示：

1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
   石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。

示例 2：

输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出：3
解释：一种移除 3 块石头的方法如下所示：

1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
   石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。

示例 3：

输入：stones = [[0,0]]
输出：0
解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。

提示：

• 1 <= stones.length <= 1000
• 0 <= x_i, y_i <= 10⁴
• 不会有两块石头放在同一个坐标点上

题解

容易得到：

1. 对于两个石子A和B，如果二者同行/列，那么A和B属于同一集合；
2. 对于石子A、B、C，如果A、B属于同一集合，且B、C属于同一集合，那么A、C属于同一集合；
3. 对于一个大小为 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();
    }