Number of Provinces

Info

Use DFS with to find all the provinces in $O(N^2)$ time.

Union Find Solution

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
 
        parent = [i for i in range(n)]
 
        def find(x):
            # If a node is not the godfather
            if x != parent[x]:
                parent[x] = find(parent[x])
                return parent[x]
            
            return x
        
        def union(x, y):
            # If both have the same parent
            if find(x) == find(y):
                return False
            
            # Union step
            parent[find(x)] = find(y)
 
            return True
 
 
        provinces = n
        for i in range(n):
            for j in range(n):
                if i != j and isConnected[i][j]:
                    if union(i, j):
                        provinces -= 1
        
        return provinces

BFS Solution

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        adj = [[] for i in range(n)]
        for i in range(n):
            for j in range(n):
                if i != j and isConnected[i][j]:
                    adj[i].append(j)
        
        seen = set()
        stack = []
        def bfs():
            while stack:
                for i in range(len(stack)):
                    node = stack.pop()
                    if node not in seen:
                        seen.add(node)
                        for adjNode in adj[node]:
                            stack.append(adjNode)
        
        provinces = 0
        for i in range(n):
            if i not in seen:
                provinces += 1
                stack.append(i)
                bfs()
 
        return provinces

DFS Solution

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # n cities
            # transitivity rule between cities
        
        # Algo:
            # Run DFS for number of islands
                # Since if you run DFS, it will find out the number of groups, in which all such groups have connections, and the rest don't!
 
        n = len(isConnected)
 
        # 1. Form an adjacency matrix with the information on isConnected
        adj = defaultdict(list)
        for i in range(n):
            for j in range(n):
                if i != j and isConnected[i][j]:
                    adj[i].append(j)
 
        # print(adj)
 
        # 2. Run DFS to find out the "number of islands"
        seen = set()
        def dfs(node):
            if node in seen:
                return
 
            seen.add(node)
 
            for adjNode in adj[node]:
                dfs(adjNode)
 
        provinces = 0
        for node in range(n):
            if node not in seen:
                provinces += 1
                dfs(node)
 
        return provinces

---

References

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