大家好， 好久不见，最近在上海已经隔离麻了，后面有空和大家聊聊隔(坐)离(牢)生活。
毕竟上海哪儿都挺好的，就是我在上海。
今天和大家分享一篇干货，讲解并查集的原理和优化，相信学会此篇文章，以后笔试/面试遇到并查集的题目都可以做出来！
以一个直观的问题来引入并查集的概念。
亲戚问题：有一群人，他们属于不同家族，同一个家族里的人互为亲戚，不同家族的人不是亲戚。随机指定两个人，问他们是否有亲戚关系。
以下图3个不相交的集合表示3个家族，当询问两个人是否有亲戚关系时，也就是问两个元素是否在同一个集合中，例如3-7有亲戚关系，3-4没有亲戚关系。
本章将介绍的并查集就是用来处理如上问题的数据结构。
通用描述如下，并查集是一种描述不相交集合的数据结构，若一个问题涉及多个元素，可划归不同集合，同属一个集合内的元素等价（即可用任意一个元素作为代表），不同集合内的元素不等价。
当我们问某些元素是否等价时，例如亲戚问题中问两人否互为亲戚关系时，就可以用不相交集来解决。
这类问题的初始状态通常是每一个元素构成一个单元素集合，后续通过合并操作将等价元素归入一个集合中。
因此处理过程中通常要用到查询（元素属于哪个集合，用于决定是否要执行合并）及合并集合的操作。
故此，不相交集也叫并查集，“不相交”描述的是问题对象构成集合之后不同集合不相交的状态，“并查”描述的是处理问题时的操作。本章中两种称呼都会出现。
本章余下内容，我们会以LeetCode 547: 省份数量问题来理解不相交集及其并查操作，该问题描述如下。
LeetCode 547. 省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例1:
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例2
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3这是一个典型的不相交集问题。
如果我们能够通过矩阵信息将同一省份的城市都加入到同一个集合，那么最终这些不相交集合的数量就是省份数量。
容易思考出这样的处理过程：
1时的两个城市合并在一起得到一个2元素的集合。之后当某个单元素集合或者2元素集合要再与一个2元素集合合并时，我们需要判断这两个元素是否不在一个集合中，这需要一个查询元素所属集合的操作。在查询操作中，我们容易想到以树的结构来实现，以根节点作为代表这个集合的代表元，每个元素指向一个父节点，循环地向上查询，一定能查询到根节点。
查询两个节点元素的根是否相同，即可知道他们是否属于同一集合。
由此我们初步构想出不相交集处理问题的主要过程：初始化、合并和查询。
以树的语言来说明不相交集如何处理上述省份问题。
创建一个数组parent[]，下标代表元素(树的节点)，总长度即总元素个数，值为父节点下标，一棵树中只有根节点以自己为父节点。
开始时每个节点都是以自己为根的单节点树，即parent[x] = x。如下初始化过程通常在main方法或并查集类(UnionFind)的构造方法中完成。
// 初始化
int[] parent = new int[isConnected.length];
for(int i = 0; i < isConnected.length; i++) {
parent[i] = i;
}假设输入如下，一共有6个城市{0, 1, 2, 3, 4, 5}，isConnected\[i][j] = 1表示i与j直接相连。
// 输入矩阵M
{
{1, 0, 0, 0, 1, 0}, // 0-0, 0-4
{0, 1, 0, 0, 0, 1}, // 1-1, 1-5
{0, 0, 1, 1, 0, 1}, // 2-2, 2-3, 2-5
{0, 0, 1, 1, 0, 0}, // 3-2, 3-3
{1, 0, 0, 0, 1, 0}, // 4-0, 4-4
{0, 1, 1, 0, 0, 1}, // 5-1, 5-2, 5-5
}初始化后得到如下5棵单节点树(单元素集合)。
接着遍历矩阵，执行合并。合并的依据是查询，对于x和y，如果find(x) = find(y)，说明代表元相同，属于同一集合，不必合并。
若find(x) != find(y)，将其合并，令parent[find(y)] = find(x)（ 或parent[find(x)] = find(y) ）。
从树的角度来看相当于把y挂在了x上（或把x挂在y上）。
我们现在先假设查询方法find(x)能够正常工作，该方法返回x所在树的的树根（所在集合的代表元），在接下来的「查询」小节中再给出find(x)的实现。
// 合并
public void union(int x, int y) {
if(find(x) != find(y)){
parent[find(y)] = find(x);
}
}这里需要强调的是，代表元可以是集合中的任意一个元素，所以一开始选谁做根(代表元)是无关紧要的，
在遍历过程中对于每一次isConnected[i][j] = 1，都执行一次union(i, j)，不断扩大集合。遍历结束时得到的每个集合都对应一个省份。
如下图，实际上输入矩阵前三行遍历完成后，我们就已经得到了最终的不相交集，此输入对应的输出为2，即原输入矩阵中存在2个省份。
※ 省份数量可以在union方法内添加一行代码(发生合并时令unionCount++)实现累计，最后以元素总数减去合并次数得到不相交集数量。
也可以在合并完成后对所有元素执行一次find(x)，统计不同结果的个数得到。这不是本节的重点故不写出此过程。
在合并前需要查询元素所在树的根节点，由于不相交集都是一棵树，每一个节点x都以parent[x]指向其父节点，根的父节点为其自身，故可以用递归的方式查询一个节点的根节点。
// 查询
public int find(int x) {
if(parent[x] == x){ // 只有根节点满足parent[x] = x
return x;
} else{
return find(parent[x]);
}
}至此我们得到了典型的不相交集实现，主要方法find和union都只有数行代码，十分简洁。
前面我们以较为简单的输入分析了查询及合并的过程，若考虑集合元素较多的情形，我们将可能得到一棵较高的树，例如上述{1, 2, 3, 5}这个集合，连续地与单节点集合{6}, {7}, {8}执行union(6, 5), union(7, 5), union(8, 5)之后，将得到如下。
不难发现，简单直接的合并将有可能导致较高的树高，若再继续执行union(5, 9)，首先进行的find(5)将会依次向父节点方向查询1, 2, 6, 7, 8，查询效率低下。
如果我们能将树的高度降低，例如除根节点外的所有节点直接挂在根节点下，那么find(x)的复杂度将为常数级。
沿着这个思路，下一节我们将介绍两种更好的求并方法，使得两棵树合并后得到的新树树高较小。
补充说明：寻找等价关系
在省份问题中，由于矩阵已给出等价信息，我们可以直接求并。
对于有的问题，开始时等价信息并不明显，需要先找到这样的等价关系，然后通过求并将初始的单元素集合合并成2元素集合。
例如LeetCode 128: 最长连续序列问题，可以用不相交集求解，但需要在开始时对 i 和 i+1 执行一次合并操作。具体过程请参考「例题」中的题解。
以目前的实现求解省份问题，我们已经发现，合并 x 和 y 所在树时，只是简单地将y所在树的根指向x所在树的根parent[find(y)] = find(x)，最坏的情况下我们将得到一棵链状的树，较高的树高将导致较高的查询(及合并)复杂度。
一个显然的好做法是将一棵树除根外的所有节点都直接指向根节点，这样在查询任意一个节点时，都只需一步即可返回所在树的树根。因此我们希望以某种策略使合并后得到树高较小的树，下面我们将介绍两种改进的求并法。
若一棵树拥有越多的节点，其高度倾向于越高。因此在合并前先比较两棵树的大小，将较小树的根连接到较大树的根以完成合并。
代码需要添加保存集合(树)大小的数组和该数组的初始化内容。
如下代码在构造方法中初始化树大小数组size[]。
// 初始化
int[] parent = new int[isConnected.length];
for(int i = 0; i < isConnected.length; i++) {
parent[i] = i;
}
UnionFind uf = new UnionFind(parent);
// UnionFind类(部分)
class UnionFind{
private int[] parent;
private int[] size; // 保存树的大小
public UnionFind(int[] parent) {
this.parent = parent;
this.size = new int[parent.length];
for (int i = 0; i < parent.length; i++) {
this.size[i] = 1; // 初始时单节点树大小为1
}
}
}按大小求并。
// 该方法在UnionFind类中
public void union(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
// 根节点不同才求并
if(xRoot != yRoot) {
if(size[yRoot] <= size[xRoot]){
parent[yRoot] = xRoot; // 较小者的根挂在较大者根上
size[xRoot] += size[yRoot]; // 新树大小为原树大小之和
} else {
parent[xRoot] = yRoot;
size[yRoot] += size[xRoot];
}
}
}有时，一棵大小较小的树反而高于较大的树，直接按高度求并比按大小求并能更准确地使每次合并后的新树高度较小。
另外，不同于按大小求并时每次合并均修改新树的大小信息，按高度求并时，新树的高度变化只发生在两棵树高度相等时，此时高度加1。
※ 关于名称：若程序中所有的求并操作都是通过本节方法实现，则可严格地称其为按高度求并。
但后续将介绍一种find()的优化版本，该优化版本在查询的同时也完成一部分合并操作，应用此版本的查询方法将导致某些时刻rank[root]与树的实际高度不相等，严谨起见，通常称作按“秩(rank)”求并。
详细内容在「路径压缩」一节叙述。
// 初始化
int[] parent = new int[isConnected.length];
for(int i = 0; i < isConnected.length; i++) {
parent[i] = i;
}
UnionFind uf = new UnionFind(parent);
// UnionFind类(部分)
class UnionFind{
private int[] parent;
private int[] rank; // 保存树秩
public UnionFind(int[] parent) {
this.parent = parent;
this.rank = new int[parent.length];
for (int i = 0; i < parent.length; i++) {
this.rank[i] = 1; // 初始时单节点树的秩为1
}
}
}按秩(高度)求并。
// 该方法在UnionFind类中
public void union(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
// 根节点相同不影响结果，最终还是会得到根节点指向自己的结果
// 在不同集合元素求并操作较多时，省去xRoot != yRoot的判断效率较高
if(rank[yRoot] <= rank[xRoot]){
parent[yRoot] = xRoot;
} else {
parent[xRoot] = yRoot;
}
// 当两棵树秩相等且为不同集合时，新树的高度加1
// 注意，秩较小的树的秩无需更新，因为每次求一个元素所在集合的高度都会先找到该集合的树的根，
// 秩较小的树在合并后其树根在新树中就不是树根了
if(rank[xRoot] == rank[yRoot] && xRoot != yRoot){
rank[xRoot]++;
}
}对前述{1, 2, 3, 5}集合，连续地与单节点集合{6}, {7}, {8}执行union(6, 5), union(7, 5), union(8, 5)，在应用按秩求并之后，将得到如下。
这样得到的树已经很理想了，但我们还会想，如果能将节点5也直接连到根节点2下，那将得到一个对于查询操作来说最完美的高度为2的树。
实际上只需在find()方法中修改一行代码，就可以让find()在查询根节点的同时执行一部分合并动作。
例如在 union(6, 5) 时，会执行 find(5)，此时让5在寻找其所在树的根节点的过程中，实时地让令其到根节点路径上的所有节点都指向根节点，就能实现对该路径节点与根节点的再次合并（指同一集合内节点指向的改变而非集合合并），结果使得原路径被压缩，所以改进后的查询操作也称作带路径压缩的查询。
只需改动else时的动作，将递归的find[parent[x]]赋值给parent[x]，就可以让当前查找的节点到根节点路径上所有的节点都指向根节点，如下。
// 带合并的路径压缩查找
public int find(int x) {
if(parent[x] == x){
return x;
} else{
// 将递归查找父节点的结果作为当前节点的父节点
// 每次回归都返回当前节点的父节点(已经被赋值为根节点了，所以每次都返回根节点)
return parent[x] = find(parent[x]);
}
}对前述{1, 2, 3, 5}集合，连续地与单节点集合{6}, {7}, {8}执行union(6, 5), union(7, 5), union(8, 5)，在应用带路径压缩的查询和按秩求并之后，将得到如下。
5指向2发生在union(6, 5)时(其内调用find(5)时)，注意到find()方法并未修改树的高度，也即此时的rank[2] = 3，但树的高度已经变为2了。
因此在应用带路径压缩的查询和按秩求并后，rank[root]记录的数字是树真实高度的一个上界，这就是通常用“秩”而非“高度“来描述的原因。
通过上述对实际问题处理过程的讲解，我们已经给出了能够处理集合代表元查询及合并问题的不相交集数据结构。
在按大小或按秩(高度)求并时，需要新建保存大小或秩(高度)信息的数组。
现给出如下包含直接求并，按大小求并，按秩(高度)求并，直接查询，带路径压缩查询等方法的实现。
实际使用时只需按需选择一种求并和一种查询方法即可，按秩求并 + 带路径压缩查询的组合在多数情况下是效率较高的选择。
class UnionFind{
private int[] parent;
private int[] rank; // 按秩求并和按大小求并选择其中一种即可
private int[] size;
public UnionFind(int[] parent) {
this.parent = parent;
this.rank = new int[parent.length];
this.size = new int[parent.length];
for (int i = 0; i < parent.length; i++) {
this.rank[i] = 1;
this.size[i] = 1;
}
}
/**
* 直接求并
*/
public void unionDirect(int x, int y) {
if(find(x) != find(y)){
parent[find(y)] = find(x);
}
}
/**
* 按大小求并
*/
public void unionBySize(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
// 根节点不同才求并
if(xRoot != yRoot) {
if(size[yRoot] <= size[xRoot]){
parent[yRoot] = xRoot;
size[xRoot] += size[yRoot];
} else {
parent[xRoot] = yRoot;
size[yRoot] += size[xRoot];
}
}
}
/**
* 按秩求并
*/
public void union(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
// 根节点相同不影响结果，最终还是会得到根节点指向自己的结果
// 在不同集合元素求并操作较多时，省去xRoot != yRoot的判断效率较高
if(rank[yRoot] <= rank[xRoot]){
parent[yRoot] = xRoot;
} else {
parent[xRoot] = yRoot;
}
// 当两棵树秩相等且为不同集合时，新树的高度加1
// 注意，秩较小的树的秩无需更新，因为每次求一个元素所在集合的高度都会先找到该集合的树的根
if(rank[xRoot] == rank[yRoot] && xRoot != yRoot){
rank[xRoot]++;
}
}
/**
* 直接查找
*/
public int findDirect(int x) {
if(parent[x] == x){
return x;
} else{
return findDirect(parent[x]);
}
}
/**
* 带路径压缩的查找
*/
public int find(int x) {
if(parent[x] == x){
return x;
} else{
// 将递归查找父节点的结果作为当前节点的父节点
// 每次回归都返回当前节点的父节点(已经被赋值为根节点了，所以每次都返回根节点)
return parent[x] = find(parent[x]);
}
}
}无需大小/秩数组空间的技巧
如果元素的表示不涉及负数（在本章例子中用非负整数来表示元素，这也是通常的做法）的话，可以用一个小技巧来节省大小或秩(高度)数组的开销。
在以前的说明中，初始化集合时，我们令每一个元素的父节点指向自己，即parent[x] = x，表示这是根节点。
本技巧以parent[x] = -1表示根节点，并以parent[x]是否为负数来判断x是否为根节点。
需要注意的是，因其为负数，在两棵树比较大小或秩(高度)时，值越小，则大小或秩(高度)越大。
在按大小求并时，size[root]的更新方法不变，但在按高度求并时，新树高度增高1时令rank[root]--。
应用此技巧，给出如下完整实现。
同样地，实际使用时只需按需选择一种求并和一种查询方法即可，按秩求并 + 带路径压缩查询的组合在多数情况下是效率较高的选择。
class UnionFind2{
private int[] parent;
public UnionFind2(int[] parent) {
this.parent = parent;
}
/**
* 直接求并
*/
public void unionDirect(int x, int y) {
if(find(x) != find(y)){
parent[find(y)] = find(x);
}
}
/**
* 按大小求并
*/
public void unionBySize(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
// 根节点不同才求并
if(xRoot != yRoot) {
if(parent[xRoot] <= parent[yRoot]){ // 负数比较，较小者树较大
parent[xRoot] += parent[yRoot];
parent[yRoot] = xRoot;
} else {
parent[yRoot] += parent[xRoot];
parent[xRoot] = yRoot;
}
}
}
/**
* 按秩求并
*/
public void union(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
// 负数比较，秩更小者树更高，将小秩树挂到大秩树上
// 在不用负数技巧的版本中，由于根节点相同不影响结果，考虑到在不同集合元素求并操作较多时，省去xRoot != yRoot的判断能提高效率
// 但在这个版本中，必须要执行xRoot != yRoot的判断，否则当两个同集合元素比较时，将使得parent[xRoot] = xRoot。
// 也即原为一个负数的parent[xRoot]的值变成了一个非负数(xRoot)，将导致程序错误
if(xRoot != yRoot) {
if(parent[xRoot] <= parent[yRoot]){
parent[yRoot] = xRoot;
} else {
parent[xRoot] = yRoot;
}
// 当两棵树秩相等根节点不同时，新树的高度增高1（负数表示，减1）
if(parent[xRoot] == parent[yRoot]){
parent[xRoot]--;
}
}
}
/**
* 直接查找
*/
public int findDirect(int x) {
if(parent[x] < 0){ // 只有代表元满足 parent[x] < 0
return x;
} else{
// 将递归查找父节点的结果作为当前节点的父节点
// 每次回归都返回当前节点的父节点(已经被赋值为根节点了，所以每次都返回根节点)
return findDirect(parent[x]);
}
}
/**
* 带路径压缩的查找
*/
public int find(int x) {
if(parent[x] < 0){ // 只有代表元满足 parent[x] < 0
return x;
} else{
parent[x] = find(parent[x]); // 将递归查找父节点的结果作为当前节点的父节点
return parent[x]; // 每次回归都返回当前节点的父节点(已经被赋值为根节点了，所以每次都返回根节点)
}
}
}
应用按秩求并和带路径压缩查询的复杂度分析。
时间复杂度：严格的分析很复杂，省略。时间复杂度为O(αn)，对于任何实际的问题，α通常不会超过5，n是程序初始时元素个数。
空间复杂度：取决于parent[] / size[] / rank[]数组所占空间，为O(n)。
在「处理过程」中我们介绍了应用不相交集处理问题的通用过程，对于不同的具体问题，各步骤的应用是灵活的。
在本节例题中我们将看到，同样是应用不相交集，对于LeetCode 128: 最长连续数列，只需在find()时以路径压缩方式合并，除给定初始时的等价关系用到主动合并(直接求并)外，不再调用union()。
在本章介绍的LeetCode 547: 省份数量中，等价关系在输入矩阵中是明显的，只需在isConnected[i][j] = 1时主动合并union(i, j)即可，find()中可以不带合并(路径压缩)，当然也可以带路径压缩以提高效率。
在LeetCode 200: 岛屿数量中，其与省份数量问题的输入都是矩阵，但岛屿数量问题的初始时单节点元素是矩阵中的每一个“1”，而省份数量问题是列(或行)中的每一个元素。此外，前者还需小心处理边界条件。
public int longestConsecutiveUF(int[] nums) {
if(nums.length < 2) {
return nums.length;
}
UnionFind uf = new UnionFind(nums);
for(int num : nums) {
uf.union(num, num + 1);
}
int max = 1;
for (int num : nums) {
max = Math.max(max, uf.find(num) - num + 1);
}
return max;
}
class UnionFind{
// 用HashMap存储并查集
Map<Integer, Integer> parents = new HashMap<>();
// 输入数组arr，初始化并查集，同时完成对arr的去重
public UnionFind(int[] arr) {
for(int i : arr) {
parents.put(i, i);
}
}
// 带路径压缩的查找
public int find(int x) {
if(x == parents.get(x)) {
return x;
}
int p = parents.get(x);
parents.put(x, find(p));
return parents.get(x);
}
// 直接求并
public void union(int x, int y) {
if(parents.containsKey(y)) {
parents.put(x, y); // rootx指向rooty
}
}
}class Solution {
// 按秩序合并的并查集
// 初始化 > 遍历grid，对“1”的格子，考察其右侧及下侧的格子，分别执行合并，
// 初始化时得到最初的岛屿总数islandsCount，按秩序合并，每次合并累计合并次数mergedCount
// 最终岛屿数量等于islandsCount-mergedCount
// 1. 初始化
// parents[k] 将二维grid[i][j]映射到一维 k = i * COL + j
// 初始化parents: grid[i][j] = 1时 parents[k] = k
// 2. 遍历grid
int islandsCount = 0;
int mergedCount = 0;
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length;
UnionFind uf = new UnionFind(grid);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int landx = i * n + j;
if(grid[i][j] == '1'){ // 以下两行，检测右侧和下侧是否联通，联通时合并之（用并列的if，在union中会检测是否属于同一集合）
if(j < n - 1 && grid[i][j + 1] == '1') { // 右侧
uf.union(landx, landx + 1);
}
if(i < m - 1 && grid[i + 1][j] == '1') { // 下侧
uf.union(landx, landx + n);
}
}
}
}
return islandsCount - mergedCount;
}
private class UnionFind{
private int[] parents;
private int[] rank;
public UnionFind(char[][] grid){
int m = grid.length, n = grid[0].length;
this.parents = new int[m * n];
this.rank = new int[m * n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++) {
if(grid[i][j] == '1'){ // 针对单格岛，累计岛屿数量，赋值parents[k] rank[k]
islandsCount++;
int k = i * n + j;
parents[k] = k;
rank[k] = 1;
}
}
}
}
// 带路径压缩的查找
public int find(int x){
if(parents[x] == x) return x;
return parents[x] = find(parents[x]);
}
// 按秩合并
public void union(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
if(xRoot != yRoot){
mergedCount++; // 只有不属于一个集合时，合并才次数加1
if(rank[yRoot] <= rank[xRoot]) parents[yRoot] = xRoot;// yRoot挂到xRoot上
else parents[xRoot] = yRoot; // xRoot挂到yRoot上
if (rank[xRoot] == rank[yRoot]) rank[xRoot]++; // 秩相同时才加1
}
}
}
}package com.yukiyama.leetcode;
/**
* 构成一个岛的1组成一个集合，岛与岛之间的关系是不相交集
* 按行或列遍历，检查当前元素的右邻和下邻元素，通过合并将每一个1都放入相应的集合
* 一开始每一个1都是一个单节点集合
* 遍历的界是比行/列少1，i < row.length - 1, j < column.length - 1
* @author lixueshan
*
*/
public class LC200NumIslands {
public static void main(String[] args) {
LC200NumIslands demo = new LC200NumIslands();
// char[][] grid = {{'1'}};
// char[][] grid = {{'1', '1'}};
char[][] grid = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
// char[][] grid = {{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
System.out.println(demo.numIslands(grid));
}
public int numIslands(char[][] grid) {
// 初始化单节点集合。
// 两层for遍历grid，令值为'1'的元素指向自己，islandNum++
// land = i*CLOUMN+j;
// parent[land] = land;
int ROW = grid.length;
int COLUMN = grid[0].length;
int[] parent = new int[ROW * COLUMN];
int[] rank = new int[parent.length];
int islandsNum = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COLUMN; j++) {
if(grid[i][j] == '1') {
islandsNum++;
int land = i * COLUMN + j;
parent[land] = land;
rank[land] = 1;
}
}
}
UnionFindLC200 uf = new UnionFindLC200(parent, rank);
// 为方便处理边界情形，向grid矩阵最后一行下添加一行（全'0'），最后一列后添加一列(全'0')
char[][] newGrid = new char[ROW + 1][COLUMN + 1];
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COLUMN; j++) {
newGrid[i][j] = grid[i][j];
}
}
for (int i = 0; i < COLUMN + 1; i++) {
newGrid[ROW][i] = '0';
}
for (int j = 0; j < ROW + 1; j++) {
newGrid[j][COLUMN] = '0';
}
// 合并集合。
// 两层for遍历grid，探测下邻和右邻，执行按秩合并，每合并一次使islandNum--
for (int i = 0; i < ROW; i++) { // 无需执行newGrid的最后一行
for (int j = 0; j < COLUMN; j++) { // 无需执行newGrid的最后一列
if(newGrid[i][j] == '1') {
if(newGrid[i][j + 1] == '1') { // 探测右邻
int landx = i * COLUMN + j;
int landy = i * COLUMN + j + 1;
uf.union(landx, landy);
}
if(newGrid[i + 1][j] == '1') { // 探测下邻
int landx = i * COLUMN + j;
int landy = (i + 1) * COLUMN + j;
uf.union(landx, landy);
}
}
}
}
return islandsNum - uf.getUnionCount();
}
}
class UnionFindLC200{
private int[] parent;
private int unionCount = 0;
private int[] rank;
public UnionFindLC200(int[] parent, int[] rank) {
this.parent = parent;
this.rank = rank;
}
/**
* 按秩求并
*/
public void union(int x, int y){
int xRoot = find(x);
int yRoot = find(y);
//
if(xRoot != yRoot) {
unionCount++;
}
if(rank[yRoot] <= rank[xRoot]){
parent[yRoot] = xRoot;
} else {
parent[xRoot] = yRoot;
}
// 当两棵树秩相等且为不同集合时，新树的高度加1
// 注意，秩较小的树的秩无需更新，因为每次求一个元素所在集合的高度都会先找到该集合的树的根
if(rank[xRoot] == rank[yRoot] && xRoot != yRoot){
rank[xRoot]++;
}
}
/**
* 带路径压缩的查找
*/
public int find(int x) {
if(parent[x] == x){
return x;
} else{
// 将递归查找父节点的结果作为当前节点的父节点
// 每次回归都返回当前节点的父节点(已经被赋值为根节点了，所以每次都返回根节点)
return parent[x] = find(parent[x]);
}
}
public int getUnionCount() {
return this.unionCount;
}
}希望疫情尽快散退！
本文由哈喽比特于2年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/gNrElu1uWuL2mi5IYhNjUg
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
