1. Depth First Search

Intuition

A province is a group of directly or indirectly connected cities. This is essentially finding the number of connected components in an undirected graph. We can use DFS to explore all cities reachable from a starting city, marking them as visited. Each time we start a new DFS from an unvisited city, we have found a new province.

Algorithm

1. Create a visited array of size n initialized to false.
2. Initialize province count res to 0.
3. For each city i from 0 to n-1:
   • If city i is not visited:
     • Increment res (found a new province).
     • Run dfs from city i to mark all connected cities as visited.
4. In the dfs:
   • Mark the current node as visited.
   • For each neighbor nei that is connected and not visited, recursively call dfs.
5. Return res.

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)

Intuition

Instead of using a separate visited array, we can use the diagonal of the adjacency matrix itself to track visited status. Since isConnected[i][i] is always 1 (a city is connected to itself), we can set it to 0 when we visit that city. This saves space but modifies the input.

Algorithm

1. Initialize province count res to 0.
2. For each city i from 0 to n-1:
   • If isConnected[i][i] equals 1 (not yet visited):
     • Increment res.
     • Run dfs from city i.
3. In the dfs:
   • Set isConnected[node][node] = 0 to mark as visited.
   • For each neighbor nei that is connected and whose diagonal is still 1, recursively call dfs.
4. Return res.

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

Intuition

BFS provides an alternative to DFS for exploring connected components. Instead of going deep first, we explore all neighbors at the current level before moving to the next. The logic remains the same: start from an unvisited city, explore all reachable cities using a queue, and count each new starting point as a separate province.

Algorithm

1. Create a visited array of size n initialized to false.
2. Initialize province count res to 0 and create an empty queue.
3. For each city i from 0 to n-1:
   • If city i is not visited:
     • Increment res.
     • Mark city i as visited and add it to the queue.
     • While the queue is not empty:
       • Dequeue a city node.
       • For each neighbor nei that is connected and not visited, mark it visited and enqueue it.
4. Return res.

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

Intuition

The Union-Find (Disjoint Set Union) data structure is designed for efficiently managing connected components. We start with each city as its own component. As we process connections, we union the components of connected cities. The final number of distinct components equals the number of provinces. Path compression and union by size optimizations make this approach nearly O(1) per operation.

Algorithm

1. Initialize a DSU with n components, where each city is its own parent.
2. For each pair of cities (i, j) where isConnected[i][j] == 1:
   • Call union(i, j) to merge their components.
   • The union operation decrements the component count if the cities were in different components.
3. Return the final component count from the DSU.

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)$

---

Common Pitfalls

Confusing Nodes with Edges

The adjacency matrix isConnected[i][j] represents whether city i and city j are directly connected. A common mistake is treating the matrix indices as edge indices rather than node indices. Remember that n is the number of cities, not the number of connections.

Forgetting to Mark Nodes as Visited

When performing DFS or BFS, failing to mark a node as visited before or immediately after processing it can lead to infinite loops or counting the same province multiple times. Always mark nodes as visited as soon as they are encountered.

Misunderstanding the Diagonal

The diagonal elements isConnected[i][i] are always 1 (a city is connected to itself). When modifying the input to track visited status, be careful to use the diagonal correctly. Do not confuse self-connections with actual inter-city connections.