难度: Hard
给你一个大小为 m x n ，由若干 0 和 1 组成的二维网格 grid ，其中 1 表示陆地， 0 表示水。岛屿 由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
一天内，可以将 任何单个 陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
示例 1：
输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]] 输出：2 解释：至少需要 2 天才能得到分离的陆地。 将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。
示例 2：
输入：grid = [[1,1]] 输出：2 解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 30grid[i][j] 为 0 或 1运行时间: 43 ms
内存: 17.2 MB
class UnionFind:
def __init__(self, n):
self.p = [i for i in range(n)]
self.k = n
def find(self, node):
if node != self.p[node]:
self.p[node] = self.find(self.p[node])
return self.p[node]
def union(self, a, b):
root_a, root_b = self.find(a), self.find(b)
if root_a != root_b:
self.p[root_a] = root_b
self.k -= 1
def tarjan_p(g, root, n):
count = 1
dfn, low, cut = [0] * n, [n] * n, [False] * n
def tarjan_p_inner(x, fa):
nonlocal count
dfn[x] = low[x] = count
count += 1
cnt = 0
for y in g[x]:
if y == fa:
continue
if dfn[y]:
low[x] = min(low[x], dfn[y])
else:
tarjan_p_inner(y, x)
low[x] = min(low[x], low[y])
if low[y] >= dfn[x]:
cnt += 1
if cnt > 1 or (x != root and cnt):
cut[x] = True
tarjan_p_inner(root, -1)
return [i for i, c in enumerate(cut) if c]
class Solution:
def minDays(self, grid: List[List[int]]) -> int:
# 目标是增大联通分量，能最小分成两部分就行
# 第一步：并查集，如果有0或大于2个连通域，答案就是0
# 第二步，tarjan判断割点，如果有答案是1，否则就是2
root = zero = 0
m, n = len(grid), len(grid[0])
uf = UnionFind(m * n)
g = [[] for _ in range(m*n)]
for i in range(m):
for j in range(n):
x = i * n + j
if i+1 < m and grid[i][j] and grid[i+1][j]:
uf.union(x, x+n)
g[x].append(x+n)
g[x+n].append(x)
root = x
if j+1 < n and grid[i][j] and grid[i][j+1]:
uf.union(x, x+1)
g[x].append(x+1)
g[x+1].append(x)
if not grid[i][j]:
zero += 1
if uf.k - zero != 1:
return 0
ans = tarjan_p(g, root, m*n)
return 1 if ans else min(2, m*n-zero)
这个题解的思路分为两个步骤： 1. 使用并查集判断初始时有多少个连通分量。如果连通分量数为0或大于2，那么答案为0，不需要改变任何陆地。 2. 如果只有一个连通分量，则使用Tarjan算法求割点。如果存在割点，则只需要删除一个割点就可以将图分成两部分，答案为1；否则需要删除两个点，答案为2。特殊情况是当全部都是陆地时，需要返回min(2, m*n)。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class UnionFind:
def __init__(self, n):
self.p = [i for i in range(n)]
self.k = n
def find(self, node):
if node != self.p[node]:
self.p[node] = self.find(self.p[node]) # 路径压缩
return self.p[node]
def union(self, a, b):
root_a, root_b = self.find(a), self.find(b)
if root_a != root_b:
self.p[root_a] = root_b # 合并连通分量
self.k -= 1 # 连通分量数减1
def tarjan_p(g, root, n):
count = 1
dfn, low, cut = [0] * n, [n] * n, [False] * n
def tarjan_p_inner(x, fa):
nonlocal count
dfn[x] = low[x] = count
count += 1
cnt = 0
for y in g[x]:
if y == fa:
continue
if dfn[y]:
low[x] = min(low[x], dfn[y])
else:
tarjan_p_inner(y, x)
low[x] = min(low[x], low[y])
if low[y] >= dfn[x]:
cnt += 1
if cnt > 1 or (x != root and cnt): # 判断割点
cut[x] = True
tarjan_p_inner(root, -1)
return [i for i, c in enumerate(cut) if c]
class Solution:
def minDays(self, grid: List[List[int]]) -> int:
# 目标是增大联通分量，能最小分成两部分就行
# 第一步：并查集，如果有0或大于2个连通域，答案就是0
# 第二步，tarjan判断割点，如果有答案是1，否则就是2
root = zero = 0
m, n = len(grid), len(grid[0])
uf = UnionFind(m * n)
g = [[] for _ in range(m*n)]
for i in range(m):
for j in range(n):
x = i * n + j
if i+1 < m and grid[i][j] and grid[i+1][j]:
uf.union(x, x+n)
g[x].append(x+n)
g[x+n].append(x)
root = x
if j+1 < n and grid[i][j] and grid[i][j+1]:
uf.union(x, x+1)
g[x].append(x+1)
g[x+1].append(x)
if not grid[i][j]:
zero += 1 # 统计水的数量
if uf.k - zero != 1: # 如果连通分量不为1，答案为0
return 0
ans = tarjan_p(g, root, m*n)
return 1 if ans else min(2, m*n-zero) # 根据割点判断最终答案
如果所有单元都是陆地，且没有任何水单元，连通分量数自然为1。根据题解逻辑，接下来会使用Tarjan算法寻找割点。若存在割点，则删除一个割点即可将陆地分为两个连通分量，答案为1。如果没有割点，则需要删除两个点来实现分离，答案为2。题解中对于这种全陆地的情况还有一个特殊处理，将答案限制为 `min(2, m*n)`，即2（因为m*n表示所有陆地单元的数量）。
并查集的处理方式在只有一列或一行的情况下并无本质区别，只是在实际合并时，需要注意边界条件。例如，如果只有一列，则只需考虑行之间的合并；如果只有一行，则只需考虑列之间的合并。在这些情况中，只有水平或垂直方向的邻接关系可用于合并。尽管合并操作的方向可能减少，但并查集的基本操作和目的（即识别和合并连通分量）保持不变。
在使用Tarjan算法处理孤立节点时，这些节点因为没有连接到其他节点，其`dfn`和`low`值将保持初始化状态，不会被更新。因此，这些孤立节点不会被视为割点，因为割点的定义是在删除该点后至少会使得一个非叶子节点变成不可达。孤立的节点已经是独立的连通分量，删除它不会影响其他节点的连通性。在实际的算法实现中，孤立节点会被自动忽略或视为单独的连通分量。
路径压缩是并查集优化技术中的一种方法，其作用是在执行查找操作（find）时减少树的高度，从而加快未来操作的速度。具体来说，当我们递归地进行find操作以找到一个节点的根节点时，路径压缩会使得路径上的每个节点都直接连接到根节点，这样以后对这些节点的查找操作都可以直接到达根节点，从而大大减少了查找路径的长度。这种方法可以显著提高并查集在处理大量合并和查找操作时的效率，特别是在节点数量非常多的情况下。