跳至主要內容

0547. 省份数量

ITCharge大约 2 分钟

0547. 省份数量open in new window

  • 标签:深度优先搜索、广度优先搜索、并查集、图
  • 难度:中等

题目链接

题目大意

描述:有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

「省份」是由一组直接或间接链接的城市组成,组内不含有其他没有相连的城市。

现在给定一个 n * n 的矩阵 isConnected 表示城市的链接关系。其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,isConnected[i][j] = 0 表示第 i 个城市和第 j 个城市没有相连。

要求:根据给定的城市关系,返回「省份」的数量。

说明

  • 1n2001 \le n \le 200
  • n==isConnected.lengthn == isConnected.length
  • n==isConnected[i].lengthn == isConnected[i].length
  • isConnected[i][j]isConnected[i][j]1100
  • isConnected[i][i]==1isConnected[i][i] == 1
  • isConnected[i][j]==isConnected[j][i]isConnected[i][j] == isConnected[j][i]

示例

  • 示例 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:并查集

  1. 遍历矩阵 isConnected。如果 isConnected[i][j] == 1,将 i 节点和 j 节点相连。
  2. 然后判断每个城市节点的根节点,然后统计不重复的根节点有多少个,即为「省份」的数量。

思路 1:代码

class UnionFind:
    def __init__(self, n):                          # 初始化
        self.fa = [i for i in range(n)]             # 每个元素的集合编号初始化为数组 fa 的下标索引
    
    def find(self, x):                              # 查找元素根节点的集合编号内部实现方法
        while self.fa[x] != x:                      # 递归查找元素的父节点,直到根节点
            self.fa[x] = self.fa[self.fa[x]]        # 隔代压缩优化
            x = self.fa[x]
        return x                                    # 返回元素根节点的集合编号

    def union(self, x, y):                          # 合并操作:令其中一个集合的树根节点指向另一个集合的树根节点
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:                        # x 和 y 的根节点集合编号相同,说明 x 和 y 已经同属于一个集合
            return False
        self.fa[root_x] = root_y                    # x 的根节点连接到 y 的根节点上,成为 y 的根节点的子节点
        return True

    def is_connected(self, x, y):                   # 查询操作:判断 x 和 y 是否同属于一个集合
        return self.find(x) == self.find(y)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        size = len(isConnected)
        union_find = UnionFind(size)
        for i in range(size):
            for j in range(i + 1, size):
                if isConnected[i][j] == 1:
                    union_find.union(i, j)

        res = set()
        for i in range(size):
            res.add(union_find.find(i))
        return len(res)

思路 1:复杂度分析

  • 时间复杂度O(n2×α(n))O(n^2 \times \alpha(n))。其中 nn 是城市的数量,α\alpha 是反 Ackerman 函数。
  • 空间复杂度O(n)O(n)