Number of Provinces (LC 547)

Pattern: Union-Find (Disjoint Set Union) — also solvable by DFS Difficulty: Medium Key Concept: Count connected components in an undirected graph given as an adjacency matrix. Each “province” is one component.

Problem Statement

There are n cities. isConnected[i][j] == 1 means city i and city j are directly connected; 0 otherwise. A province is a maximal group of directly or indirectly connected cities. Return the number of provinces.

Example

• isConnected = [[1,1,0],[1,1,0],[0,0,1]] → 2
• isConnected = [[1,0,0],[0,1,0],[0,0,1]] → 3

---

1. Algorithm & Pseudocode

Union-Find

dsu = DSU(n)         // every city in its own component initially
for i in 0..n-1:
    for j in i+1..n-1:
        if isConnected[i][j] == 1: dsu.union(i, j)
return dsu.components

DFS

visited[n] = false
count = 0
for i in 0..n-1:
    if !visited[i]: dfs(i); count++
return count

dfs(u):
    visited[u] = true
    for v in 0..n-1:
        if isConnected[u][v] == 1 and !visited[v]: dfs(v)

---

2. Step-by-Step Analysis

Why Union-Find shines The graph is given by an adjacency matrix. Each union merges two components. The final number of disjoint sets = number of provinces.

Why upper-triangular iteration The matrix is symmetric (undirected). We only need j > i to avoid double-processing edges.

Why path compression + union by rank Each find is amortized O(α(N)) — practically O(1).

ASCII Trace for n=4, edges (0,1),(1,2),(3,3)

initial: parent = [0,1,2,3]   components = 4

union(0,1): merge → parent = [1,1,2,3]   components = 3
union(1,2): merge → parent = [1,2,2,3]   components = 2
(3 self-loop ignored)
final components = 2

---

3. Java Solution

Union-Find

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

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (isConnected[i][j] == 1) {
                    int ra = find(parent, i), rb = find(parent, j);
                    if (ra != rb) {
                        if (rank[ra] < rank[rb]) parent[ra] = rb;
                        else if (rank[ra] > rank[rb]) parent[rb] = ra;
                        else { parent[rb] = ra; rank[ra]++; }
                        components--;
                    }
                }
        return components;
    }
    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}

DFS

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]) { dfs(isConnected, visited, i, n); count++; }
        }
        return count;
    }
    private void dfs(int[][] g, boolean[] visited, int u, int n) {
        visited[u] = true;
        for (int v = 0; v < n; v++)
            if (g[u][v] == 1 && !visited[v]) dfs(g, visited, v, n);
    }
}

Time: (O(n^2)) Space: (O(n))

---

4. The “Java vs. Others” Edge

• Iterative find with path compression is slightly faster than recursive; for LC inputs (n ≤ 200), recursion is fine.
• Adjacency matrix → O(n²) edge scan is unavoidable; converting to adjacency list doesn’t help here since the graph is dense.

---

5. Complexity Summary

Approach	Time	Space	Notes
Union-Find	O(n² α(n))	O(n)	α ≈ 1; effectively O(n²)
DFS	O(n²)	O(n)	Visits every matrix cell