☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Number of provinces

Medium TUF ID 535 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

There are n cities. You are given an n x n matrix isConnected where isConnected[i][j] == 1 if cities i and j are directly linked and 0 otherwise. Links are mutual (the matrix is symmetric) and every city is linked to itself (isConnected[i][i] == 1). A province is a group of cities that are linked directly or through other cities, with no city outside the group linked to any inside it. Return the number of provinces.

In graph terms: the cities are vertices, the matrix is an adjacency matrix, and a province is a connected component. The only twist compared with the usual adjacency-list input is that neighbours must be found by scanning a row.

Constraints: 1 ≤ n ≤ 200.

Example 1

isConnected = [[1,1,0],
               [1,1,0],
               [0,0,1]]
answer = 2          // {0, 1} and {2}

Example 2

isConnected = [[1,0,0,1],
               [0,1,1,0],
               [0,1,1,1],
               [1,0,1,1]]
answer = 1          // 0-3, 3-2, 2-1: everyone is linked indirectly

Example 2 is the point of the word “indirectly”: cities 0 and 1 share no direct link, yet they are in the same province through 3 and 2.

Approach 1: Brute force, transitive closure

Intuition. “Linked directly or indirectly” is the transitive closure of the “directly linked” relation. Warshall’s algorithm computes it: start with reach[i][j] true for direct links and for i == j, then for each city k in turn, allow k as an intermediate stop. If i can reach k and k can reach j, then i can reach j. After all k have been allowed, reach[i][j] says exactly whether i and j are in the same province.

To count provinces from the closure, count one representative per province: the smallest-numbered city in it. City j is the smallest in its province exactly when no city i < j can reach it.

Algorithm.

  1. Initialise reach[i][j] = (i == j) || isConnected[i][j] == 1.
  2. For k = 0..n-1, for every i with reach[i][k], for every j with reach[k][j], set reach[i][j] = true.
  3. Count the j for which no i < j has reach[i][j].
static int bruteForce(int[][] isConnected) {
    int n = isConnected.length;
    boolean[][] reach = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) reach[i][j] = i == j || isConnected[i][j] == 1;
    }
    for (int k = 0; k < n; k++) {                         // now allow k as a stop in between
        for (int i = 0; i < n; i++) {
            if (!reach[i][k]) continue;
            for (int j = 0; j < n; j++) {
                if (reach[k][j]) reach[i][j] = true;
            }
        }
    }
    int provinces = 0;
    for (int j = 0; j < n; j++) {
        boolean smallest = true;                          // is j the smallest city of its province?
        for (int i = 0; i < j; i++) {
            if (reach[i][j]) {
                smallest = false;
                break;
            }
        }
        if (smallest) provinces++;
    }
    return provinces;
}

Complexity. Time O(n^3): three nested loops over the cities. Space O(n^2) for the closure. With n ≤ 200 that is 8 million steps, which actually passes, but it computes far more than needed: the full city-to-city reachability table when we only want a count.

Why does processing k in the outer loop work? After the iteration for k, reach[i][j] is true whenever there is a route from i to j whose intermediate stops all lie in {0, ..., k}. Each new k extends that set by one, and at the end every route is allowed.

Approach 2: Optimal, DFS on the matrix

Intuition. A DFS from a city visits every city of its province and nothing else. So, as in any component count, loop over all cities, and each time you find one that is still unvisited, count a new province and run a DFS from it to mark the rest. Because the input is a matrix, the neighbours of u are found by scanning row u for ones. There is no need to convert the matrix into an adjacency list first. The conversion is legitimate (the A2Z lecture does it), but it costs the same O(n^2) scan and extra memory.

Algorithm.

  1. visited all false, provinces = 0.
  2. For each city i: if not visited, increment provinces and DFS from i.
  3. dfs(u): mark u; for every v with isConnected[u][v] == 1 and v unvisited, dfs(v).
static int optimalDfs(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        provinces++;                                      // i belongs to a province nobody has explored yet
        dfs(isConnected, i, visited);
    }
    return provinces;
}

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

Dry run on example 2:

outer i visited before action visited after
0 no provinces = 1; dfs(0) -> row 0 has 3 -> dfs(3) -> row 3 has 2 -> dfs(2) -> row 2 has 1 -> dfs(1) {0, 1, 2, 3}
1 yes skip  
2 yes skip  
3 yes skip  

Complexity. Time O(n^2): each city is entered once, and entering it scans its row of length n. That is optimal for matrix input, since the matrix itself has n^2 cells and any correct algorithm must look at them. Space O(n) for visited and the recursion, at most 200 frames deep here.

The self-links on the diagonal are harmless: when dfs(u) scans its own row, isConnected[u][u] == 1 but u is already visited, so nothing happens.

Approach 3: Optimal, union-find

Intuition. Start with every city as its own province, n in total. Each link i-j either joins two different provinces, reducing the count by one, or lies inside one province and changes nothing. Union-find tracks which province each city belongs to. Since the matrix is symmetric, only the upper triangle j > i needs to be read; the diagonal never merges anything.

Algorithm.

  1. parent[i] = i, provinces = n.
  2. For each i < j with isConnected[i][j] == 1: find the roots of i and j; if they differ, link one under the other and decrement provinces.
  3. Return provinces.
static int optimalUnionFind(int[][] isConnected) {
    int n = isConnected.length;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int provinces = n;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {                 // the matrix is symmetric, so j > i is enough
            if (isConnected[i][j] == 0) continue;
            int a = find(parent, i), b = find(parent, j);
            if (a != b) {
                parent[a] = b;
                provinces--;
            }
        }
    }
    return provinces;
}

static int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];                    // path halving
        x = parent[x];
    }
    return x;
}

Complexity. Time O(n^2 * α(n)), effectively O(n^2). Space O(n). Path halving inside find keeps the trees shallow even without union by size.

Union-find is the natural choice if links arrive one at a time and you must report the province count after each one. For a one-shot count on a matrix, DFS and union-find are equally good.

Edge cases and pitfalls