Problem of The Day: Number of Provinces

Problem Statement

leetcode problem link

My Solution [Accepted]

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        stack = []
        N = len(isConnected)
        visited = [0 for _ in range(N)]
        res = 0
        def dfs(index):
            if visited[index] == 1:
                return 0
            stack = [index]
            while stack:
                node = stack.pop()
                visited[node] = 1
                for i in range(N):
                    if i != node and isConnected[node][i] == 1 and visited[i] == 0:
                            stack.append(i)
            return 1

        for i in range(N):
            res += dfs(i)

        return res

Editorial

Approach 1: Depth First Search

class Solution:
    def dfs(self, node, isConnected, visit):
        visit[node] = True
        for i in range(len(isConnected)):
            if isConnected[node][i] and not visit[i]:
                self.dfs(i, isConnected, visit)

    def findCircleNum(self, isConnected):
        size = len(isConnected)
        numberOfComponents = 0
        visit = [False] * size

        for i in range(size):
            if not visit[i]:
                numberOfComponents += 1
                self.dfs(i, isConnected, visit)

        return numberOfComponents

Approach 2: Breadth First Search

class Solution:
    def bfs(self, node, isConnected, visited):
        from collections import deque

        queue = deque([node])
        visited[node] = True

        while queue:
            node = queue.popleft()

            for i in range(len(isConnected)):
                if isConnected[node][i] == 1 and not visited[i]:
                    queue.append(i)
                    visited[i] = True

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

        for i in range(n):
            if not visited[i]:
                numberOfComponents += 1
                self.bfs(i, isConnected, visited)

        return numberOfComponents

Approach 3: Union-find

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union_set(self, x, y):
        xset = self.find(x)
        yset = self.find(y)
        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[yset] = xset
            self.rank[xset] += 1


class Solution:
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        uf = UnionFind(n)
        numberOfComponents = n

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1 and uf.find(i) != uf.find(j):
                    numberOfComponents -= 1
                    uf.union_set(i, j)

        return numberOfComponents

Note: can implement Find() this way

def find(self, x):
    """
    Finds the root of the set containing element x without path compression.
    """
    while x != self.parent[x]:
        x = self.parent[x]
    return x