更新题目 547. Number of Provinces

题目 lc547 · 修改（rev 2） · cc · 2026-10-26 23:11
body

@@ -1,5 +1,12 @@
 ## 题目
 
-n × n 的邻接矩阵 `isConnected`，`isConnected[i][j] == 1` 表示 i 和 j 直接相连，相连关系可以传递。求连通分量（省份）的个数。
+给一个 n × n 的邻接矩阵 `isConnected`，`isConnected[i][j] == 1` 表示城市 i 和 j 直接相连。相连关系可以传递：a 连 b、b 连 c，那么 a、b、c 属于同一个省份。求省份的个数，也就是图里连通分量（connected component）的个数。
+
+LeetCode 保证矩阵对称（`isConnected[i][j] == isConnected[j][i]`），对角线全是 1，`1 <= n <= 200`。
+
+| 输入 | 输出 | 为什么 |
+| --- | --- | --- |
+| `[[1,1,0],[1,1,0],[0,0,1]]` | `2` | 0 和 1 相连是一组，2 自己一组 |
+| `[[1,0,0],[0,1,0],[0,0,1]]` | `3` | 没有任何两个城市相连，每个城市各自一组 |
 
 [LeetCode 原题](https://leetcode.com/problems/number-of-provinces/)
@@ -7,46 +14,92 @@
 ## 面经里怎么考的
 
-Visa Staff SWE OA 第二题（2026-07），题面叫 Connected Groups，矩阵元素是字符 `'1'` / `'0'`，描述和这题一致。同一场第一题是 [[q:visa-perfect-substring]]。
+Visa Staff SWE OA 第二题（2026-07），题面叫 Connected Groups，矩阵元素是字符 `'1'` / `'0'`，描述和这题一致。楼主没写题号，对应到 547 是按描述推断的【推断】。同一场第一题是 [[q:visa-perfect-substring]]。
+
+按这里的记录，OA 版和 LeetCode 原题的差别在输入格式：矩阵叫 `related`，是字符串数组，`related[i][j]` 是单个字符（未核实，原帖的确切写法待核对）。在输入是字符的前提下，比较时要写 `'1'`，见「易错点」第一条。下面的代码对字符串列表（如 `["110", "110", "001"]`）和字符二维列表都能用。OA 的 n 上限现在没有记录（未核实），所以代码不依赖 `n <= 200`。
 
 ## 思路
 
-并查集（union-find）：每对相连的 i、j 合并一次，合并成功一次分量数减一。也可以从每个没访问过的点做一次 DFS，DFS 的次数就是答案。
+用并查集（union-find）。开始时每个城市自成一组，组数是 n。扫一遍矩阵，每遇到一对直接相连的 i、j，就把它们所在的两组合并。两组本来不同、合并成功了，组数减一。两组本来就是同一组（比如 0 连 1、1 连 2 之后再看到 0 连 2），什么都不做。扫完剩下的组数就是答案。
+
+这样数是对的，原因是每次成功合并恰好让两个不同的组变成一个，组数恰好少一。扫完以后，任意两个能通过一串直接相连走到的城市都已被并进同一组，而走不到的城市之间从没被合并过，所以最后每组正好是一个连通分量。
+
+> [!say] I start with every node in its own group and union each directly connected pair. Each successful union merges two different groups, so the count drops by exactly one. Whatever remains at the end is the number of connected groups.
+
+在矩阵对称的前提下，只扫上三角（`j > i`）就够了，`(j, i)` 和 `(i, j)` 是同一条边。对角线 `(i, i)` 是城市和自己，不用看。
+
+另一种做法是从每个还没访问过的城市出发做一次 DFS 或 BFS，把能走到的城市都标成已访问，出发的次数就是答案。复杂度一样是 `O(n²)`。交卷用并查集，原因是它没有递归深度的问题，见「易错点」第三条。
 
 ## 代码
 
 ```python
-def find_circle_num(is_connected):
-    n = len(is_connected)
-    parent = list(range(n))
+from typing import Sequence
 
-    def find(a):
-        while parent[a] != a:
-            parent[a] = parent[parent[a]]   # 路径压缩
-            a = parent[a]
-        return a
 
-    groups = n
+class UnionFind:
+    """Disjoint sets over 0..size-1 with path halving and union by size."""
+
+    def __init__(self, size: int) -> None:
+        self.parent = list(range(size))
+        self.set_size = [1] * size
+        self.set_count = size
+
+    def find(self, node: int) -> int:
+        while self.parent[node] != node:
+            self.parent[node] = self.parent[self.parent[node]]  # path halving
+            node = self.parent[node]
+        return node
+
+    def union(self, a: int, b: int) -> bool:
+        """Merge the sets of a and b. Return False if they were already one set."""
+        root_a, root_b = self.find(a), self.find(b)
+        if root_a == root_b:
+            return False
+        if self.set_size[root_a] < self.set_size[root_b]:
+            root_a, root_b = root_b, root_a
+        self.parent[root_b] = root_a
+        self.set_size[root_a] += self.set_size[root_b]
+        self.set_count -= 1
+        return True
+
+
+def count_groups(related: Sequence[Sequence[str]]) -> int:
+    """Count connected groups in a symmetric '1'/'0' adjacency matrix.
+
+    related[i][j] == '1' means i and j are directly connected.
+    Accepts a list of strings (["110", ...]) or a list of char lists.
+    An empty matrix has 0 groups.
+    """
+    n = len(related)
+    groups = UnionFind(n)
     for i in range(n):
-        for j in range(i + 1, n):
-            if is_connected[i][j] == 1:     # OA 版本是字符 '1'
-                ri, rj = find(i), find(j)
-                if ri != rj:
-                    parent[ri] = rj
-                    groups -= 1
-    return groups
+        for j in range(i + 1, n):  # symmetric: the upper triangle is enough
+            if related[i][j] == '1':
+                groups.union(i, j)
+    return groups.set_count
 ```
 
-本机跑过官方例子。
+这次 OA 的代码写法也计分，所以代码这样拆：
+
+- 并查集单独写成 `UnionFind` 类，`union` 返回是否真的合并了，组数由类自己维护。主函数只剩「扫矩阵、遇到 `'1'` 就合并」，读的人一眼能看出在数什么。
+- 并查集同时用路径压缩（path halving，`find` 时把路过的点挂到祖父节点下）和按大小合并（union by size，合并时把小的那组挂到大的那组下面）。两样都用，`find` 的均摊代价才是 `O(α(n))`，见「复杂度」。
+- 边界写进 docstring：空矩阵返回 0。`related[i][j]` 对字符串和字符列表都能取到单个字符，两种输入格式都能直接传进来。
+- 做 LeetCode 原题时，输入是整数，把 `'1'` 改成 `1`。
+
+2026-10-26 用 Python 3.13.17 跑过上面这段代码：
+
+- 两个例子写成字符串列表 `["110", "110", "001"]` 和 `["100", "010", "001"]`，分别得 2 和 3。第一个例子写成字符二维列表也得 2。空矩阵得 0，`["1"]` 得 1。
+- 和 BFS 暴力解对拍：2000 个随机对称矩阵（n 从 1 到 9，连边概率随机），结果全部一致。
+- 比较整数 `1` 的 LeetCode 写法在同一组字符输入上的结果，见「易错点」第一条。
+- n = 200 全是 `'1'` 时得 1，约 5 毫秒。n = 2000 的一条链（只有相邻城市相连）得 1。
 
 ## 复杂度
 
-O(n² · α(n))，读矩阵本身就是 O(n²)。
+时间 `O(n² · α(n))`，其中 `α(n)` 是反阿克曼函数，在任何实际的 n 下都不超过 4，可以当成常数。扫上三角要看 `n(n-1)/2` 个格子，读矩阵本身就是 `O(n²)`，这一项决定了总时间。每个格子最多一次 `union`，在路径压缩和按大小合并同时用的前提下，每次 `find` 均摊是 `O(α(n))`。只用其中一样时，`α(n)` 这个界就没有保证了（只按大小合并时单次 `find` 最坏是 `O(log n)`），面试时说 `α(n)` 要连同这个前提一起说。
+
+额外空间 `O(n)`，存 `parent` 和 `set_size`。
 
 ## 易错点
 
-- OA 版本给的是字符串数组（`related[i][j]` 是字符），比较时用 `'1'`。
-- 只看上三角就够，矩阵是对称的。
-
-## 英文讲法
-
-> [!say] I union every directly connected pair and decrement the group count on each successful union; what remains is the number of connected groups.
+- **字符和整数比较**。输入是字符时要比较 `'1'`。把 LeetCode 版的 `related[i][j] == 1` 直接用在字符输入上，`'1' == 1` 永远是 `False`，一次也不合并，永远返回 n。实测例子 `["110", "110", "001"]`：比较 `'1'` 的版本得 2，比较整数 `1` 的 LeetCode 写法得 3。把同一个矩阵转成整数再给 LeetCode 写法，得 2。第二个例子答案本来就是 3，两版都得 3，所以只跑这个例子发现不了这个错。
+- **只扫上三角依赖矩阵对称**。LeetCode 保证对称，OA 版现在没有记录（未核实）。拿不准时扫整个矩阵（`j` 从 0 到 n-1），`union` 对已经在一组的两点什么都不做，结果不变，只多花一倍时间。
+- **递归 DFS 的深度**。Python 默认递归深度上限是 1000（见 [[p:me/python-pitfalls]]「数值和递归」）。实测递归 DFS 在 n = 200 的链上得 1，在 n = 2000 的链上抛 `RecursionError`，并查集版本在同一个 n = 2000 的链上得 1。LeetCode 的 n 不超过 200 不会触发，OA 的上限未核实，用 DFS 时改成显式栈。
更新题目 547. Number of Provinces

body

meta
