并查集：武林教派大乱斗
数据结构中有些高级的数据结构，但大部分实现起来并没有什么难度，本文就来吃透并查集。
并查集用于处理不相交集合的查询和合并的数据结构，其核心语句就一条，下面用一个故事带你串起并查集的实现和使用。
一、一个故事吃透并查集：武林之争
在武林之中有n个教派。我们用数组sects[]表示某个教派的老大是谁
int[] sects = new int[n + 1]; // 从0 ~ n-1也可以，根据题意和喜好
各个教派之间互不干扰，仍然处于和平发展阶段，此时各个教派都认为自己是老大。
for (int i = 1; i <= n; i++)
sects[i] = i; // 自己是老大
然后，各个教派之间的斗争就开始了。
两个教派相遇则必是一场大战，所以在开战之前，各个教派都要通过find()函数找到各自的老大来助力。（此时教派之间还没有合并，所以找到的老大是自己）
public int find(int x) {
return sects[x];
}
找到老大后，两个教派a和b在战场上正式交战了
int bossA = find(a);
int bossB = find(b);
他们之间交手，我们假设bossA胜出，此时bossB就要被boosA吞并，bossB的老大就变成了bossA。(假设bossB胜出也可以)
int bossA = find(a);
int bossB = find(b);
sects[bossB] = boosA;
但因为武林之中有很多门派，所以是一场大乱斗，各个门派疯狂吞并，所以有时会出现两个门派找到的老大是同一个人，所以当老大不是同一个人时，才会发生吞并。
这里我们就完成了union()方法
public void union(int a, int b) {
int bossA = find(a);
int bossB = find(b);
if (boosA != bossB) sects[bossB] = boosA;
}
在经历的一段时间的大乱斗之后，找老大变成了很困难的事情。门派z找到了他的老大y，但没想到y也曾被x吞并过，y有他的老大x，x又可能有他的老大…，所以找老大变成了一项体力活。
只有当找到了最终的老大（假设为m），那个没有输过的老大，也就是认他自己就是老大的m，才会返回
public int find(int x) {
if (sects[x] == x)
return sects[x];
return find(sects[x]);
}
但战场上可不能让找老大而磨去了时间，所以为了尽快的找到最终的老大，小弟之间达成共识：如果z的老大是y，y的老大是x，那么z应该直接去找x，也就是“路径压缩”：直接让z的老大指向y的老大
public int find(int x) {
if (sects[x] == x)
return sects[x];
return sects[x] = find(sects[x]); // 路径压缩
}
这便是并查集的核心方法find()，如果用一条语句表示：
public int find(int x) {
return x == sects[x] ? x : (sects[x] = find(sects[x]));
}
最后，武林经过腥风血雨，有的教派合并成一个大的教派，而有的没有。
到这里故事就结束了，我们得到了sects[]，可以借助sects[]来判断两个教派是否属于同一个老大。
二、并查集的主要方法
如果理解了上面的故事，方法就非常好写了，并且可以在方法之中随意的改变达到我们想要的效果。
并查集核心语句：find()
public int find(int x) {
return x == sects[x] ? x : (sects[x] = find(sects[x]));
}
并查集初始化：
int[] sects = new int[n + 1];
for (int i = 1; i <= n; i++)
sects[i] = i;
并查集合并方法：union()
public void union(int a, int b) {
int bossA = find(a);
int bossB = find(b);
if (boosA != bossB) sects[bossB] = boosA;
}
union()并非是死的，if (boosA != bossB)是否多余了？
如果题目要求判断这两个教派是否已经属于同一个教派：
public boolean union(int a, int b) {
int bossA = find(a);
int bossB = find(b);
if (boosA == bossB)
return true;
sects[bossB] = boosA;
return false;
}
而究竟是sects[bossB] = boosA还是sects[bossA] = boosB也是有讲究的，读者可以自己研究一下
三、并查集实战
1、LeetCode 547 省份数量
先创建并查集，再写上find()方法，然后遍历合并就好。
问题是怎么得到答案？
其实答案就是我们所说的最终的老大的数量。如果某一个城市没有被吞并，它会作为一个集合的老大，而一个集合只有一个老大（因为sects[bossB] = boosA），所以得到那些sects[i] == i的省的数量即可
int[] provinces;
public int findCircleNum(int[][] isConnected) {
int len = isConnected.length;
int ans = 0;
provinces = new int[len];
// 并查集
for (int i = 0; i < len; i++)
provinces[i] = i;
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++)
if (isConnected[i][j] == 1) {
int a = find(i);
int b = find(j);
if (a != b)
provinces[b] = a;
}
for (int i = 0; i < len; i++)
if (provinces[i] == i)
ans++;
return ans;
}
private int find(int x) {
if (x== provinces[x])
return x;
return provinces[x] = find(provinces[x]);
}
2、LeetCode 684 冗余连接
一样的思路，创建并查集，写出find()方法，在合并的时候如果发现已经属于同一个相交集则记录一下即可
int[] fa;
public int[] findRedundantConnection(int[][] edges) {
fa = new int[edges.length + 1];
for (int i = 1; i <= edges.length; i++)
fa[i] = i;
int[] ans = new int[2];
for (int[] cur : edges) {
int a = find(cur[0]);
int b = find(cur[1]);
if (a != b) fa[a] = b;
else ans = cur;
}
return ans;
}
private int find(int index) {
return index == fa[index] ? index : (fa[index] = find(fa[index]));
}
3、LeetCode 130 被围绕的区域
这题并查集并不是最优解，但并查集的解法十分巧妙，可以为并查集的使用拓展思路
首先依然是创建并查集并写出find()方法，这里的并查集创建可以使用一维数组
fa = new int[rows * cols + 1];
借用函数getIndex将二维的下标转化成一维
private int getIndex(int i, int j) {
return i * cols + j;
}
其中与边界相连的区域都会被并到同一个集合中，这就是为什么长度要+1
final outer = rows * cols;
fa[outer] = outer; // 与边界相邻的区域的集合
if (adjoinTheBound(x, y)) { // 如果当前的x，y与边界相邻
union(getIndex(x, y), outer);
}
基于dfs完成主要的方法体
final int[] dx = new int[]{-1, 0, 1, 0}; // 行数变化
final int[] dy = new int[]{0, -1, 0, 1}; // 列数变化
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'X')
continue;
// 每个点的四个方向搜索
for (int dir = 0; dir < 4; dir++) {
int next_x = i + dx[dir];
int next_y = j + dy[dir];
// 如果next直接出界，那么当前的i，j就是与边界相邻
if (next_x < 0 || next_x >= rows || next_y < 0 || next_y >= cols) {
int cur = find(getIndex(i, j));
if (cur != outer)
fa[cur] = outer; // 连接到外部
} else if (board[next_x][next_y] == 'O') { // 反之，如果next是O则需要合并
int a = find(getIndex(next_x, next_y));
int b = find(getIndex(i, j));
// 如果next已经处于outer集合中，则把当前的getIndex(i，j)放入outer集合中
if (a == outer)
fa[b] = outer;
else // 否则让next放入getIndex(i，j)的集合中
fa[a] = b;
}
}
}
所以答案就是寻找那些没有进入outer集合中的'O'，将其变成'X'
int[] fa;
int rows, cols;
public void solve(char[][] board) {
// 上 左 下 右
final int[] dx = new int[]{-1, 0, 1, 0}; // 行数变化
final int[] dy = new int[]{0, -1, 0, 1}; // 列数变化
this.cols = board[0].length;
this.rows = board.length;
final int outer = rows * cols;
fa = new int[rows * cols + 1]; // 并查集
// init
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
fa[getIndex(i, j)] = getIndex(i, j);
fa[outer] = outer;
// dfs
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'X')
continue;
// 每个点的四个方向搜索
for (int dir = 0; dir < 4; dir++) {
int next_x = i + dx[dir];
int next_y = j + dy[dir];
// 如果next直接出界，那么当前的i，j就是与边界相邻
if (next_x < 0 || next_x >= rows || next_y < 0 || next_y >= cols) {// 出界
int cur = find(getIndex(i, j));
if (cur != outer)
fa[cur] = outer; // 连接到外部
} else if (board[next_x][next_y] == 'O') { // 反之，如果next是O则需要合并
int a = find(getIndex(next_x, next_y));
int b = find(getIndex(i, j));
// 如果next已经处于outer集合中，则把当前的getIndex(i，j)放入outer集合中
if (a == outer)
fa[b] = outer;
else // 否则让next放入getIndex(i，j)的集合中
fa[a] = b;
}
}
}
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (board[i][j] == 'O' && find(getIndex(i, j)) != outer) // 没连接到外部的
board[i][j] = 'X';
}
// 二维下标转一维
private int getIndex(int i, int j) {
return i * cols + j;
}
private int find(int x) {
return x== fa[x] ? x: (fa[x] = find(fa[x]));
}
4、实战题目
LeetCode 990 等式方程的可满足性
LeetCode 721 账户合并