Leetcode 547 Solution

This article provides solution to leetcode question 547 (number-of-provinces)
Categories:
Tags:
Access this page by simply typing in "lcs 547" in your browser address bar if you have bunnylol configured.

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

Solution

class FindUnionSet:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))



    def union(self, i, j):
        ri = self.find(i)
        rj = self.find(j)
        self.parents[ri] = rj



    def find(self, i):
        if self.parents[i] != i:
            self.parents[i] = self.find(self.parents[i])
        return self.parents[i]




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



        fmset = FindUnionSet(n)



        for i in range(n):
            for j in range(n):
                if isConnected[i][j]:
                    fmset.union(i, j)



        roots = set()
        for i in range(n):
            roots.add(fmset.find(i))



        return len(roots)