1. 并查集
并查集解決的是不相交集合的合并及查詢問題仇让。并查集的本質(zhì)是一種樹形數(shù)據(jù)結(jié)構(gòu)躺翻，每個(gè)集合對(duì)應(yīng)一棵樹。當(dāng)需要執(zhí)行“合并兩個(gè)元素所在集合”類似操作時(shí)踊淳，則可能會(huì)用到并查集陕靠。
在并查集中脱茉，每個(gè)節(jié)點(diǎn)指向其父節(jié)點(diǎn)垄开，而根節(jié)點(diǎn)的父節(jié)點(diǎn)為其自身，而根節(jié)點(diǎn)本身就可以代表整個(gè)集合虚吟。即签财，對(duì)于一個(gè)節(jié)點(diǎn)，如果通過遞歸調(diào)用父節(jié)點(diǎn)唱蒸，最終可以追溯到某個(gè)根節(jié)點(diǎn)，那么該節(jié)點(diǎn)就屬于這個(gè)根節(jié)點(diǎn)所代表的集合庆捺。
在執(zhí)行合并兩個(gè)元素所在集合（即合并兩個(gè)節(jié)點(diǎn)所在的樹）操作時(shí)滔以，并查集會(huì)首先檢查兩個(gè)節(jié)點(diǎn)所在樹的根節(jié)點(diǎn)是否是同一個(gè)氓拼；如果是的話，則說明不需要合并桃漾；反之，則使其中一個(gè)根節(jié)點(diǎn)成為另一個(gè)根節(jié)點(diǎn)的子節(jié)點(diǎn)适滓。
通俗地講恋追，并查集就相當(dāng)于若干“原始部落”，每個(gè)節(jié)點(diǎn)都是部落的成員苦囱，而根節(jié)點(diǎn)就是部落的“首領(lǐng)”。子節(jié)點(diǎn)的查詢就相當(dāng)于成員找到上級(jí)朽砰，上級(jí)又找到上級(jí)的上級(jí)喉刘，最后追溯到部落的首領(lǐng)。而集合的合并就相當(dāng)于部落的兼并造锅，兩個(gè)部落合并成一個(gè)廉邑，首領(lǐng)只剩一個(gè)，另一個(gè)則俯首稱臣（成為另一個(gè)根的子節(jié)點(diǎn)）糙箍。
1.1 并查集的特點(diǎn)
并查集有以下特點(diǎn)：
- 包含一個(gè)或若干樹狀結(jié)構(gòu)深夯，每棵樹代表一個(gè)集合收奔，每個(gè)節(jié)點(diǎn)代表集合中的一個(gè)元素；
- 樹中節(jié)點(diǎn)只知道自己的父節(jié)點(diǎn)饰剥；
- 根節(jié)點(diǎn)的父節(jié)點(diǎn)為其自身；
- 可以執(zhí)行合并操作顾孽，將兩個(gè)節(jié)點(diǎn)所在的樹合并成一棵樹比规；合并之后测秸，一棵樹的根節(jié)點(diǎn)成為另一棵樹根節(jié)點(diǎn)的子節(jié)點(diǎn)。
1.2 并查集的一般形式
/**
* 并查集
*
* @param <T> 節(jié)點(diǎn)類型
*/
public class UnionFind<T> {
protected int size;
protected final Map<T, T> parent = new HashMap<>();
/**
* @param orig 原始數(shù)據(jù)集
*/
public UnionFind(T[] orig) {
for (T t : orig) {
parent.put(t, t); // 每個(gè)節(jié)點(diǎn)作為一個(gè)根節(jié)點(diǎn)
}
size = orig.length;
}
/**
* 合并兩個(gè)節(jié)點(diǎn)所在的樹
*/
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--;
}
}
/**
* 查詢節(jié)點(diǎn)node所在樹的根節(jié)點(diǎn)
*/
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 城市道路系統(tǒng)問題
輸入一個(gè)整型數(shù)組
int[] cities铃拇，每個(gè)元素代表一個(gè)城市缠俺；
輸入若干對(duì)整數(shù)int[][] roads磷雇，每對(duì)整數(shù)表示對(duì)應(yīng)的兩個(gè)城市之間修建有道路。
如果城市之間能通過道路到達(dá)睁本，那么稱這些城市處于同一個(gè)道路系統(tǒng)凡泣。
問：總共有多少個(gè)道路系統(tǒng)？
假設(shè)城市數(shù)組為{1,2,3,4,5,6,7,8,9}猴誊，
道路為{1,2}, {3,4}, {4,5}, {6,8}, {1,6}, {9,5}。
并查集的思路：
首先把每個(gè)原始數(shù)據(jù)各自分割成一個(gè)集合：{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}焚辅；
因?yàn)樽詈蠛喜⒊闪?個(gè)集合瘫析，故一共有3個(gè)道路系統(tǒng)。
例題代碼實(shí)現(xiàn)：
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();
}
其中并查集的代碼為第一節(jié)中的一般形式奇适。
2.2 例2 Leetcode 947. 移除最多的同行或同列石頭
題目Leetcode 947. 移除最多的同行或同列石頭
題解Leetcode 947. 移除最多的同行或同列石頭
題目：
n 塊石頭放置在二維平面中的一些整數(shù)坐標(biāo)點(diǎn)上趋急。每個(gè)坐標(biāo)點(diǎn)上最多只能有一塊石頭键科。
如果一塊石頭的 同行或者同列 上有其他石頭存在，那么就可以移除這塊石頭茄厘。
給你一個(gè)長(zhǎng)度為 n 的數(shù)組 stones 吆录，其中 stones[i] = [xi, yi] 表示第 i 塊石頭的位置，返回 可以移除的石子 的最大數(shù)量侄柔。
示例 1：
輸入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
輸出：5
解釋：一種移除 5 塊石頭的方法如下所示：
- 移除石頭 [2,2] ，因?yàn)樗?[2,1] 同行。
- 移除石頭 [2,1] ，因?yàn)樗?[0,1] 同列。
- 移除石頭 [1,2] 乔宿，因?yàn)樗?[1,0] 同行。
- 移除石頭 [1,0] 详瑞，因?yàn)樗?[0,0] 同列。
- 移除石頭 [0,1] 泻帮，因?yàn)樗?[0,0] 同行驳庭。
石頭 [0,0] 不能移除，因?yàn)樗鼪]有與另一塊石頭同行/列饲常。
示例 2：
輸入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
輸出：3
解釋：一種移除 3 塊石頭的方法如下所示：
- 移除石頭 [2,2] 贝淤，因?yàn)樗?[2,0] 同行。
- 移除石頭 [2,0] 播聪，因?yàn)樗?[0,0] 同列布隔。
- 移除石頭 [0,2] 衅檀，因?yàn)樗?[0,0] 同行霎俩。
石頭 [0,0] 和 [1,1] 不能移除，因?yàn)樗鼈儧]有與另一塊石頭同行/列杉适。
示例 3：
輸入：stones = [[0,0]]
輸出：0
解釋：[0,0] 是平面上唯一一塊石頭柳击，所以不可以移除它。
提示：
- 1 <= stones.length <= 1000
- 0 <= xi, yi <= 104
- 不會(huì)有兩塊石頭放在同一個(gè)坐標(biāo)點(diǎn)上
題解
容易得到：
- 對(duì)于兩個(gè)石子A和B蹬叭，如果二者同行/列哭靖，那么A和B屬于同一集合；
- 對(duì)于石子A试幽、B铺坞、C洲胖，如果A、B屬于同一集合擒滑，且B叉弦、C屬于同一集合，那么A淹冰、C屬于同一集合；
- 對(duì)于一個(gè)大小為
n的石子集合柠衍，可以移除n - 1枚石子。
遍歷數(shù)組stones珍坊，對(duì)于每一個(gè)石子{x, y}，天然都屬于兩個(gè)集合：第x行禽最、第y列。于是川无，將第x行與第y列的石子合并成一個(gè)新的集合即可虑乖。
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列"，其中用負(fù)數(shù)代替第y列
}
return stones.length - uf.size();
}
