Course4all
Join us on telegram
Home/dsa/Union Find/Number of Provinces

Number of Provinces

Master this topic with zero to advance depth.

Number of Provinces

Given an n×nn \times n matrix isConnected where isConnected[i][j] = 1 if city ii and city jj are directly connected. Return the total number of provinces (connected components).

Medium

Examples

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

Level I: DFS (Component Counting)

Intuition

Treat the matrix as an adjacency list. For each city, if not visited, start a DFS to visit all cities in its province. Count the number of DFS starts.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

City 0: unvisited. Count=1. DFS(0) visits City 1. City 1: visited. City 2: unvisited. Count=2. DFS(2).

java
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, count = 0;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { count++; dfs(isConnected, visited, i); }
        }
        return count;
    }
    private void dfs(int[][] m, boolean[] v, int i) {
        v[i] = true; for (int j = 0; j < m.length; j++) if (m[i][j] == 1 && !v[j]) dfs(m, v, j);
    }
}
Approach 2

Level III: Union-Find (Component ID)

Intuition

Standard DSU application. For every connection, perform a union. The answer is the initial city count minus successful unions.

⏱ O(N^2 \cdot \alpha(N))💾 O(N)

Detailed Dry Run

3 Cities. Initial count=3. Union(0,1) -> success, count=2. Connection(0,2)=0 -> no union. Connection(1,2)=0 -> no union.

java
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, count = n;
        int[] p = new int[n]; for (int i = 0; i < n; i++) p[i] = i;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    int r1 = find(p, i), r2 = find(p, j);
                    if (r1 != r2) { p[r1] = r2; count--; }
                }
            }
        }
        return count;
    }
    private int find(int[] p, int i) { return p[i] == i ? i : (p[i] = find(p, p[i])); }
}
← Previous QuestionGraph Valid Tree
Next Question →Accounts Merge