更新题目 547. Number of Provinces
题目 lc547 · 修改（rev 3） · · 2026-10-27 00:33
body
@@ -1,5 +1,5 @@ ## 题目 -给一个 n × n 的邻接矩阵 `isConnected`，`isConnected[i][j] == 1` 表示城市 i 和 j 直接相连。相连关系可以传递：a 连 b、b 连 c，那么 a、b、c 属于同一个省份。求省份的个数，也就是图里连通分量（connected component）的个数。 +给一个 $n \times 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`。 @@ -102,4 +102,4 @@ - **字符和整数比较**。输入是字符时要比较 `'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` 对已经在一组的两点什么都不做，结果不变，只多花一倍时间。 +- **只扫上三角依赖矩阵对称**。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 时改成显式栈。
meta
@@ -2,5 +2,5 @@ "lc_slug": "number-of-provinces", "depth_guide": "2026-10-23", - "rewritten_by": "cloud:20261026-1620", + "rewritten_by": "cloud:20261026-2312", "rewritten_at": "2026-10-27" }