0547. 省份数量

[giscus[bot]]

0547. 省份数量

--- 0547. 省份数量 标签：深度优先搜索、广度优先搜索、并查集、图 难度：中等 题目链接 0547. 省份数量 - 力扣 题目大意 描述：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 「省份」是由一组直接或间接链接的城市组成，组内不含...

https://algo.itcharge.cn/solutions/0500-0599/number-of-provinces/

[xiaos2021]

小优化：设置计数器cnt = n，每次合并前判断是否已连通，未连通则操作一次合并并且cnt减1，最后cnt数值就是结果。

class Solution:
    def __init__(self):
        self.fa = []
    
    def initFa(self, N):
        self.fa = list(range(N))
    
    def find(self, x):
        while self.fa[x] != x:
            self.fa[x] = self.fa[self.fa[x]]
            x = self.fa[x]
        return x
    
    def isCon(self, x, y):
        return self.find(x) == self.find(y)
    
    def join(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.fa[rx] = ry

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        self.initFa(n)

        cnt = n
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] and (not self.isCon(i, j)):
                    self.join(i, j)
                    cnt -= 1
        return cnt