Skip to main content

547. Number of Provinces - LeetCode

· One min read
from ..notes import Uf


class Solution:
    # https://leetcode.com/problems/number-of-provinces/solutions/923039/union-find-with-union-by-ranks-and-path-compression/
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        uf = Uf(list(range(len(isConnected))))
        for i in range(len(isConnected)):
            for j in range(i + 1, len(isConnected)):
                if isConnected[i][j]:
                    uf.union(i, j)
        return len(set(uf.find(x) for x in range(len(isConnected))))