Problem 22.4 · Depth-First SearchMedium

Number of Provinces

PatternGraph DFS and Flood Fill Union-Find

What it teaches: Components when the graph is given as an adjacency matrix.

Practise it on judges as “Number of Provinces”.

The problem

isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of cities connected directly or indirectly. Return the number of provinces.

Example 1

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Constraints

1 ≤ n ≤ 200
Symmetric, with 1s on the diagonal

Pattern clues in the wording

→ Count groups
→ Adjacency matrix input

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int findCircleNum(int[][] isConnected) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	isConnected = [[1,1,0],[1,1,0],[0,0,1]]	2
2	isConnected = [[1,0,0],[0,1,0],[0,0,1]]	3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. DFS over the matrix · O(n²)2. Union-find · O(n² α(n))

DFS over the matrix

Time O(n²) Space O(n)

For each unvisited city, count++ and DFS; neighbours of i are all j with isConnected[i][j] = 1.

Approach 1

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, count = 0;
        boolean[] seen = new boolean[n];
        for (int i = 0; i < n; i++)
            if (!seen[i]) { count++; dfs(isConnected, i, seen); }
        return count;
    }

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

Verdict: The matrix size dominates.

Union-find

Time O(n² α(n)) Space O(n)

Start with n groups; union i and j for every 1 above the diagonal; each successful union reduces the count.

Approach 2

class Solution {
    private int[] parent;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, groups = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (isConnected[i][j] == 1) {
                    int a = find(i), b = find(j);
                    if (a != b) { parent[a] = b; groups--; }
                }
        return groups;
    }

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

Verdict: Same cost; preview of Module 25.

Before you submit

Edge cases and common mistakes

Test these inputs

Everyone connected
Nobody connected

Mistakes people make

Treating the matrix as a grid of land cells (it's an adjacency matrix).

Interview

Follow-up questions

Why scan the whole row for neighbours?

Command Palette