547. Number of Provinces - Explanation

Description

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the i-th city and the j-th city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [
    [1,1,0],
    [1,1,0],
    [0,0,1]
]

Output:  2

Example 2:

Input: isConnected = [
    [1,0,1],
    [0,1,1],
    [1,1,1]
]

Output: 1

Constraints:

1 <= n <= 200
n == isConnected.length == isConnected[i].length
isConnected[i][j] is either 0 or 1.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        res = 0
        visited = [False] * n

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

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

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Depth First Search (Modifying Input)

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

        def dfs(node):
            isConnected[node][node] = 0
            for nei in range(n):
                if node != nei and isConnected[node][nei] and isConnected[nei][nei]:
                    dfs(nei)

        for i in range(n):
            if isConnected[i][i]:
                dfs(i)
                res += 1

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$ for recursion stack.

3. Breadth First Search

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        res = 0
        q = deque()

        for i in range(n):
            if not visited[i]:
                res += 1
                visited[i] = True
                q.append(i)
                while q:
                    node = q.popleft()
                    for nei in range(n):
                        if isConnected[node][nei] and not visited[nei]:
                            visited[nei] = True
                            q.append(nei)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Disjoint Set Union

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)
        self.components = n

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False

        self.components -= 1
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True
    
    def numOfComps(self):
        return self.components

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

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

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$