23.06.04 Today’s Leetcode

547. Number of Provinces (medium)

Union-find Approach, graph

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * 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):
        xset, yset = self.find(x), self.find(y)
        if xset != yset:
            if self.rank[xset] < self.rank[yset]:
                self.parent[xset] = yset
            elif self.rank[xset] > self.rank[yset]:
                self.parent[yset] = xset
            else:
                self.parent[xset] = yset
                self.rank[yset] += 1
            return True
        return False

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        d = DSU(n)
        for i in range(n):
            for j in range(n):
                v = isConnected[i][j]
                if v == 1:
                    d.union(i, j)

        print(d.parent)
        print(d.rank)
        return len(set(d.parent))

Simple DFS

class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        provinces = 0
        visited = [False] * n

        def dfs(node):
            visited[node] = True
            for neighbor in range(n):
                if isConnected[node][neighbor] == 1 and not visited[neighbor]:
                    dfs(neighbor)

        for i in range(n):
            if not visited[i]:
                provinces += 1
                dfs(i)

        return provinces