Number of Provinces

LeetCode 547 | Difficulty: Medium

Medium

Problem 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,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

- `1 <= n <= 200`

- `n == isConnected.length`

- `n == isConnected[i].length`

- `isConnected[i][j]` is `1` or `0`.

- `isConnected[i][i] == 1`

- `isConnected[i][j] == isConnected[j][i]`

Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

Union-Find

Maintain disjoint sets with two operations: find (which set does element belong to?) and union (merge two sets). Use path compression and union by rank for near O(1) amortized operations.

When to use

Connected components, cycle detection in undirected graphs, grouping elements.

---

Solutions

Solution 1: C# (Best: 112 ms)

Metric	Value
Runtime	112 ms
Memory	28.6 MB
Date	2020-01-29

Solution

public class Solution {
    public int FindCircleNum(int[][] M) {
       bool[] visited = new bool[M.Length];
    int count = 0;
    for (int i = 0; i < M.Length; i++)
    {
        if(!visited[i])
        {
            count++;
            visited[i] = true;
            dfs(M, visited, i);
        }
    }
    return count;
}

public void dfs(int[][] M, bool[] visited, int person)
{
    for (int other = 0; other < M.Length; other++)
    {
        if(!visited[other] && M[person][other] == 1)
        {
            visited[other] = true;
            dfs(M, visited, other);
        }
    }
}

}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$
Union-Find	$O(n × α(n))$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.