547 Number of Provinces

https://leetcode.com/problems/number-of-provinces/

solution

• union find

class UF:
    def __init__(self, n):
        self.parents = list(range(n))
    
    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]
    
    def union(self, parent, child):
        self.parents[self.find(child)] = self.find(parent)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        uf = UF(n=len(isConnected))

        for i in range(len(isConnected)):
            for j in range(i):
                if isConnected[i][j] == 1:
                    uf.union(i, j)

        res = []
        for i in range(len(isConnected)):
            if uf.find(i) not in res:
                res.append(uf.find(i))
        return len(res)

时间复杂度：O() 空间复杂度：O()

• dfs