Number of Provinces

Q: 省份数量的时间复杂度是多少？

使用图搜索或并查集，时间复杂度都是 O(n²)，因为两者都会读取一次 n × n 矩阵中的每个元素。并查集还会增加一个 α(n) 因子，即反阿克曼函数，这个值在实际中最多为 4。额外空间复杂度为 O(n)。

Q: 解决“省份数量”问题时，你应该使用 DFS、BFS 还是并查集？

这三种方法都返回相同的数量，时间复杂度为 O(n²)。DFS 或 BFS 写起来最简洁。如果你还需要回答许多“这两个城市是否属于同一个省”的问题，那么并查集是更好的工具，因为每次查询都只需接近常数时间。

Q: 省份数量与岛屿数量有什么不同？

两者都会统计连通分量。在 Number of Islands 中，图是一个网格，每个方格最多有四个邻居，工作量为 O(rows × cols)。这里的图是一个邻接矩阵：任意城市都可以与其他城市相连，列出一个城市的邻居需要读取一整行的 n 个条目。

中等并查集图

+10

有 n 个城市，编号从 0 到 n-1。当一条道路直接连接城市 i 和城市 j 时，isConnected[i][j] 的值为 1，否则为 0。道路是双向的，因此这个矩阵是对称的，并且每个城市都与自身相连。

省份是由一组城市组成的，这些城市可以直接或通过其他城市彼此到达，并且没有道路通向这组城市之外。返回省份的数量。

函数

findCircleNum(isConnected: integer-2d-array) → integer

isConnectedinteger-2d-array: n × n 矩阵，如果一条道路直接连接两座城市，则填入 1
返回值integer: 省份数量

约束条件

1 ≤ n ≤ 150，其中 n = isConnected.length
isConnected[i].length = n
isConnected[i][j] 是 0 或 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

示例

输入: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
输出: 2
解释: 城市 0 有一条通往城市 3 的道路，城市 1 有一条通往城市 2 的道路。这两组城市之间没有道路相连，所以共有 2 个省份。

进阶

现在，每条道路都会在指定的一天开放。你能找出所有城市都属于同一个省份的第一天吗？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

这个矩阵描述的是一个无向图：城市是节点，每个 1 表示一条边。省份是一个连通分量；如果第三座城市连接了两座城市，那么它们之间的 0 不会将它们分开。从每个未访问过的城市开始搜索，或者对每条边使用并查集，都能在 O(n²) 时间内统计连通分量的数量。

从每个未访问的城市开始进行深度优先搜索

思路

未标记的城市不可能属于你已经统计过的省份，因为每次搜索都会标记整个省份。因此，它会开启一个新的省份。搜索会沿着矩阵的各行进行：在第二个示例中，从城市 0 开始的搜索会到达城市 1，而城市 1 所在的行接着会到达城市 2，尽管第 0 行中城市 2 对应的值是 0。

每个城市只会弹出一次，并读取它所在行的 n 个条目，因此你只需读取一次矩阵：时间复杂度为 O(n²)。标记和栈最多保存 n 个城市，因此额外空间复杂度为 O(n)。

算法

为每个城市创建一个已访问标记，并将计数设为 0。
按顺序遍历城市，跳过已访问的城市。
遇到未访问的城市时，将计数加 1，标记该城市，并将它压入栈中。
只要栈中还有城市，就弹出一个，并将它所在行中值为 1 且尚未访问的每个城市压入栈中，同时在压入时标记它们。
返回计数。

def findCircleNum(isConnected):
    n = len(isConnected)
    seen = [False] * n
    provinces = 0
    for start in range(n):
        if seen[start]:
            continue
        # Nobody reached this city from an earlier province, so it starts a new one.
        provinces += 1
        seen[start] = True
        stack = [start]
        while stack:
            city = stack.pop()
            row = isConnected[city]
            for other in range(n):
                # Mark a city when you push it, so it is never pushed twice.
                if row[other] == 1 and not seen[other]:
                    seen[other] = True
                    stack.append(other)
    return provinces

结合路径压缩和按秩合并的并查集

思路

从 n 个省开始，每个城市各自属于一个省。对角线以上的每个 1 都表示两个城市属于同一组：如果它们所属的组不同，就合并这两组，并将省的数量减 1。在第二个示例中，数量从 5 开始，(0, 1) 将城市 0 和 1 合并，(1, 2) 将城市 2 并入它们所在的组，最后剩下 3 个省。

并查集将每个组存储为一棵树：parent[c] 指向上一级；当 find 分别沿着两个城市的路径找到同一个根节点时，这两个城市就属于同一组。如果不做优化，合并操作可能会形成一条很长的路径，每次 find 都要走 O(n) 步。按秩合并会将较矮的树挂到较高的树下面，因此路径长度不会超过 log n。路径压缩会让 find 经过的每个城市直接指向根节点。两者结合后，每次 find 的均摊时间复杂度为 O(α(n))，而在实际应用中，α(n) 至多为 4。

算法

为每个城市设置 parent[c] = c 和 rank[c] = 0，并将计数设为 n。
对于每一对满足 i < j 且 isConnected[i][j] = 1 的城市，查找 i 和 j 的根节点。
在 find 中，先沿着路径向上找到根节点，再沿原路径走一遍，将路径上的每个城市都指向根节点。
如果根节点不同，就将秩较低的根节点挂到另一个根节点下；如果秩相同，就将秩加 1，并将计数减 1。
返回计数。

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    rank = [0] * n

    def find(city):
        root = city
        while parent[root] != root:
            root = parent[root]
        # Path compression: point every city on the way straight at the root.
        while parent[city] != root:
            up = parent[city]
            parent[city] = root
            city = up
        return root

    provinces = n
    for i in range(n):
        for j in range(i + 1, n):  # the matrix is symmetric, so the upper half is enough
            if isConnected[i][j] == 1:
                a, b = find(i), find(j)
                if a == b:
                    continue
                # Union by rank: hang the shorter tree under the taller one.
                if rank[a] < rank[b]:
                    a, b = b, a
                parent[b] = a
                if rank[a] == rank[b]:
                    rank[a] += 1
                # Two provinces just became one.
                provinces -= 1
    return provinces

易错点和边界情况

只相信直接相连的道路。第二个示例中的城市 0 和 2 之间有一个 0，但它们仍然属于同一个省份。
统计 1 的数量再除以 2。三个城市彼此相连时，共有三条道路，但只有一个省份。
在并查集中，每遇到一个 1 都减少计数，而不是只在两个根不同的时候减少。
比较 parent[i] 和 parent[j]。同一组中的两个城市可能有不同的父节点，因为其中一个城市所在的层级更深。请比较 find(i) 和 find(j)。
直接连接城市 j，例如 parent[j] = find(i)。如果 j 已经属于某个组，该组的其余部分就不会合并进来。

常见问题3

省份数量的时间复杂度是多少？

使用图搜索或并查集，时间复杂度都是 O(n²)，因为两者都会读取一次 n × n 矩阵中的每个元素。并查集还会增加一个 α(n) 因子，即反阿克曼函数，这个值在实际中最多为 4。额外空间复杂度为 O(n)。

解决“省份数量”问题时，你应该使用 DFS、BFS 还是并查集？

这三种方法都返回相同的数量，时间复杂度为 O(n²)。DFS 或 BFS 写起来最简洁。如果你还需要回答许多“这两个城市是否属于同一个省”的问题，那么并查集是更好的工具，因为每次查询都只需接近常数时间。

省份数量与岛屿数量有什么不同？

两者都会统计连通分量。在 Number of Islands 中，图是一个网格，每个方格最多有四个邻居，工作量为 O(rows × cols)。这里的图是一个邻接矩阵：任意城市都可以与其他城市相连，列出一个城市的邻居需要读取一整行的 n 个条目。

def findCircleNum(isConnected):
    # 在这里编写代码

测试 #1

测试 #2

参数

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

预期输出