547. 省份数量

Difficulty
Medium
Tags
并查集
URL
https://leetcode-cn.com/problems/number-of-provinces/
Star
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：
notion imagenotion image
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：
notion imagenotion image
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
提示：
  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] 为 1 或 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]
通过次数179,189提交次数289,396

法1 并查集

思路
通过并查集来统计有几个集合
题解
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        uf = Unionfind(len(isConnected))
        for i in range(0, len(isConnected)):
            for j in range(0, i):
                if isConnected[i][j] == 1:
                    uf.union(i, j)

        res = 0
        # 有几个集合 就说明有几个 省份
        # 判断有几个集合， 只需要判断根节点即可
        for i in range(len(isConnected)):
            if uf.find(i) == i:
                res += 1

        return res

class Unionfind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def find(self, x):
        # 在查找的时候，同时进行 路径压缩
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            self.parent[root_x] = root_y