Problem Overview

You are given an n x n matrix isConnected where isConnected[i][j] = 1 means that city i and city j are directly connected, and isConnected[i][j] = 0 means they are not.

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

The task is to determine how many provinces exist in total.

Example 1:

Input: isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]
Output: 2
Explanation: Cities 0 and 1 form one province; city 2 forms another.

Example 2:

Input: isConnected = [
  [1,0,0],
  [0,1,0],
  [0,0,1]
]
Output: 3
Explanation: Each city is isolated, so there are 3 provinces.

Constraints:

• 1 <= n <= 200
• isConnected[i][j] is either 0 or 1.
• isConnected[i][i] = 1 (a city is always connected to itself).
• The graph is undirected: if isConnected[i][j] = 1, then isConnected[j][i] = 1.

---

Intuition / Approach

The problem can be modeled as a graph problem:

• Each city represents a node.
• Each connection represents an edge.
• The task is to find the number of connected components in the graph.

If two cities are connected directly or through a series of other cities, they belong to the same province.

This can be solved efficiently using either Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find (Disjoint Set Union).

We’ll explore all three briefly but implement the DFS approach since it’s straightforward and intuitive.

---

Approach 1: Depth-First Search (DFS)

Idea

We traverse the graph and mark all cities that belong to a single province.
Each time we start a new DFS from an unvisited city, it represents a new province.

Steps:

1. Initialize a boolean array visited of size n to track visited cities.
2. Loop through all cities:
   • If a city is not visited, perform a DFS starting from that city.
   • Increment the province count after each DFS call.
3. In DFS, mark the current city as visited and recursively visit all connected cities.

---

Java Code Implementation (DFS)

public class NumberOfProvinces {
    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]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }

        return provinces;
    }

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

    public static void main(String[] args) {
        NumberOfProvinces solution = new NumberOfProvinces();

        int[][] isConnected1 = {
            {1, 1, 0},
            {1, 1, 0},
            {0, 0, 1}
        };
        System.out.println(solution.findCircleNum(isConnected1)); // Output: 2

        int[][] isConnected2 = {
            {1, 0, 0},
            {0, 1, 0},
            {0, 0, 1}
        };
        System.out.println(solution.findCircleNum(isConnected2)); // Output: 3
    }
}

---

Step-by-Step Example

Let’s take isConnected = [[1,1,0], [1,1,0], [0,0,1]].

1. Start with city 0:
   • Visit 0, mark visited.
   • From 0, go to 1 (since isConnected[0][1] = 1).
   • Visit 1.
   • From 1, go back to 0 (already visited), so stop.
     → Completed one DFS traversal → 1 province found.
2. City 1 is already visited, skip it.
3. City 2 is not visited → start DFS from 2.
   • Visit 2.
   • No other connections.
     → Another province found.

Total = 2 provinces.

---

Complexity Analysis

Time Complexity: O(n²)

• We iterate through the adjacency matrix once, visiting each possible pair of cities.

Space Complexity: O(n)

• For the visited array and recursion stack (in the worst case, all cities are connected).

---

Approach 2: Breadth-First Search (BFS)

You can replace DFS with a queue-based BFS traversal.

private void bfs(int[][] isConnected, boolean[] visited, int start) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int city = queue.poll();
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[city][j] == 1 && !visited[j]) {
                visited[j] = true;
                queue.offer(j);
            }
        }
    }
}

This approach produces the same result but avoids recursion depth issues.

---

Approach 3: Union-Find (Disjoint Set Union)

Union-Find (DSU) is another elegant approach.
You initially assume each city is its own province.
Then, for each connection (i, j), you perform a union operation.
The number of unique roots after processing all connections gives the number of provinces.

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (isConnected[i][j] == 1) {
                union(parent, i, j);
            }
        }
    }

    Set<Integer> provinces = new HashSet<>();
    for (int i = 0; i < n; i++) {
        provinces.add(find(parent, i));
    }
    return provinces.size();
}

private int find(int[] parent, int x) {
    if (parent[x] != x)
        parent[x] = find(parent, parent[x]);
    return parent[x];
}

private void union(int[] parent, int a, int b) {
    int rootA = find(parent, a);
    int rootB = find(parent, b);
    if (rootA != rootB)
        parent[rootB] = rootA;
}

This is especially efficient for sparse graphs.

---

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
DFS	O(n²)	O(n)	Simple and clean recursive method
BFS	O(n²)	O(n)	Avoids recursion stack
Union-Find	O(n² * α(n))	O(n)	Efficient for large, sparse graphs

(α(n) is the inverse Ackermann function, which grows extremely slowly — practically constant.)