Number of Provinces

Link: Number of Provinces

Problem Statement

Given an n x n matrix isConnected, where isConnected[i][j] = 1 indicates that the i-th and j-th cities are directly connected, and 0 otherwise, a province is a group of directly or indirectly connected cities, with no external connections.

Return the total number of provinces.

Examples

Example 1

Input:

isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]

Output: 2

Explanation:

• Cities 0 and 1 are connected.

• City 2 is isolated.

• So, there are 2 provinces.

Example 2

Input:

isConnected = [
  [1,0,0],
  [0,1,0],
  [0,0,1]
]

Output: 3

Each city is isolated, forming its own province.

Constraints

• 1 <= n <= 200

• isConnected[i][j] is 0 or 1

• isConnected[i][i] == 1

Intuition

This is a connected components in a graph problem.

• Each city is a node.

• A 1 at isConnected[i][j] represents an undirected edge between nodes i and j.

We're being asked to count the number of connected components in the graph — each one is a province.

Approaches:

• DFS: Visit all cities reachable from a city.

• BFS: Same as DFS but level-order.

• Union-Find: Efficient for dynamic connectivity problems (optional for now).

Approach 1: DFS (Depth-First Search)

Key Idea

1. Maintain a visited[] array.

2. Iterate through all nodes. If a node hasn't been visited:

   • Run DFS from that node.

   • Increment the province count.

3. Each DFS traversal marks all cities in a single province.

Java Code

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinceCount = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinceCount++;
            }
        }

        return provinceCount;
    }

    private void dfs(int[][] graph, boolean[] visited, int node) {
        visited[node] = true;
        for (int j = 0; j < graph.length; j++) {
            if (graph[node][j] == 1 && !visited[j]) {
                dfs(graph, visited, j);
            }
        }
    }
}

Dry Run

Input:

isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]

Step-by-step:

• visited = [false, false, false]

• i = 0 → not visited

  • DFS visits 0 → sees 1 → DFS visits 1 → both marked visited.

  • Province count = 1

• i = 1 → already visited

• i = 2 → not visited

  • DFS visits 2

  • Province count = 2

Final Output: 2

Time & Space Complexity

Approach 2: BFS (Breadth-First Search)

Key Idea

• Instead of recursion, use a queue to explore the graph level by level.

Java Code

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(i);

                while (!queue.isEmpty()) {
                    int current = queue.poll();
                    visited[current] = true;

                    for (int j = 0; j < n; j++) {
                        if (isConnected[current][j] == 1 && !visited[j]) {
                            queue.offer(j);
                        }
                    }
                }

                provinces++;
            }
        }

        return provinces;
    }
}

Time & Space Complexity (BFS)

Applications

• Social Networks: Finding groups of people connected directly or indirectly.

• Computer Networks: Detecting disconnected sub-networks.

• Geography/Logistics: Identifying isolated cities or islands.

• Cluster Analysis: Identifying separate clusters in data science or ML.

• Epidemiology: Modeling isolated infection clusters or regions.