Definition
- Province – a connected group of cities where you can travel between any two cities in the group through direct connections.
- Adjacency matrix – a symmetric n*n matrix where isConnected[i][j]=1 means city i and j are directly connected.
- Union-Find approach – start with n separate groups; for each 1 in the upper triangle, union the two cities. Each successful union decrements the count.
- Result – the remaining count after all unions is the number of connected components (provinces).
National Bank of India groups its regional hubs into provinces based on who shares a direct data line. If hub i and hub j share a line, they are in the same province. Count the hubs, merge every directly connected pair, and the separate groups that remain are the provinces.
Understanding the Concepts
What is the Number of Provinces problem?
Given an n*n adjacency matrix where isConnected[i][j] = 1 means city i and city j are directly connected, return the number of provinces. A province is a group of cities where every city is reachable from every other city in the group.
At the National Bank of India, regional hubs are described by a connectivity matrix and the network team needs the number of independent provinces for failover planning.
package com.bank.network;
public class ProvincesDemo {
public static void main(String[] args) {
int[][] isConnected = {
{1, 1, 0},
{1, 1, 0},
{0, 0, 1}
};
System.out.println("Provinces: " + findCircleNum(isConnected));
}
static int findCircleNum(int[][] m) {
int n = m.length;
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int count = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (m[i][j] == 1 && union(parent, rank, i, j)) {
count--;
}
}
}
return count;
}
static int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
static boolean union(int[] parent, int[] rank, int a, int b) {
int ra = find(parent, a), rb = find(parent, b);
if (ra == rb) return false;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++;
return true;
}
}
Provinces: 2
How does Union-Find count connected components?
Start with n cities, each in its own group (count = n). For every pair (i, j) where isConnected[i][j] == 1 and i < j, attempt a union. If the two cities were in different groups, the union succeeds and the count decrements by 1. If they were already in the same group, nothing changes.
// Step by step for matrix:
// [[1,1,0],[1,1,0],[0,0,1]]
// Initial: count=3, groups: {0}, {1}, {2}
// i=0, j=1: m[0][1]=1 -> union(0,1) succeeds -> count=2
// i=0, j=2: m[0][2]=0 -> skip
// i=1, j=2: m[1][2]=0 -> skip
// Final: count=2, groups: {0,1}, {2}
Why scan only the upper triangle?
The matrix is symmetric: isConnected[i][j] == isConnected[j][i]. Scanning both directions would process each edge twice, which wastes work. The diagonal is always 1 (a city is connected to itself) and is skipped by starting j at i+1.
// Full scan (redundant):
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) // includes diagonal and lower triangle
if (i != j && m[i][j] == 1) union(i, j);
// Upper triangle only (efficient):
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) // skip diagonal and lower triangle
if (m[i][j] == 1) union(i, j);
What is the DFS alternative?
Instead of Union-Find, you can run DFS from each unvisited city and count the number of DFS calls. Each call discovers one connected component.
package com.bank.network;
public class ProvincesDFS {
static int findCircleNum(int[][] m) {
int n = m.length;
boolean[] visited = new boolean[n];
int provinces = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(m, visited, i);
provinces++;
}
}
return provinces;
}
static void dfs(int[][] m, boolean[] visited, int city) {
visited[city] = true;
for (int j = 0; j < m.length; j++) {
if (m[city][j] == 1 && !visited[j]) {
dfs(m, visited, j);
}
}
}
public static void main(String[] args) {
int[][] m = {{1,1,0},{1,1,0},{0,0,1}};
System.out.println("Provinces (DFS): " + findCircleNum(m));
}
}
Provinces (DFS): 2
How does Union-Find compare to DFS?
| Approach | Time | Space | Best For |
|----------|------|-------|----------|
| Union-Find | O(n^2 * alpha(n)) | O(n) | Dense matrix |
| DFS | O(n^2) | O(n) stack | Dense matrix |
| Union-Find on edge list | O(E * alpha(n)) | O(n) | Sparse graph |
| DFS on adjacency list | O(n + E) | O(n + E) | Sparse graph |
Both are O(n^2) for a dense matrix. Union-Find shines when you have an edge list (sparse graph) and need incremental connectivity.
What is the complete banking example?
Here is the full network hub connectivity analysis for the National Bank of India.
package com.bank.network;
public class HubConnectivity {
public static int countProvinces(int[][] connectivity, String[] hubNames) {
int n = connectivity.length;
int[] parent = new int[n];
int[] rank = 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++) {
if (connectivity[i][j] == 1) {
int ri = find(parent, i), rj = find(parent, j);
if (ri != rj) {
if (rank[ri] < rank[rj]) { int t = ri; ri = rj; rj = t; }
parent[rj] = ri;
if (rank[ri] == rank[rj]) rank[ri]++;
provinces--;
}
}
}
}
return provinces;
}
static int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
public static void main(String[] args) {
String[] hubs = {"Mumbai", "Delhi", "Chennai", "Kolkata"};
int[][] conn = {
{1, 1, 0, 0},
{1, 1, 0, 0},
{0, 0, 1, 1},
{0, 0, 1, 1}
};
int p = countProvinces(conn, hubs);
System.out.println("Independent provinces for failover: " + p);
}
}
Independent provinces for failover: 2
What are the edge cases?
Edge cases include n=1 (one city, one province), a fully connected matrix (one province), and a fully disconnected matrix (n provinces).
// n=1: [[1]] -> 1 province
// Fully connected 3x3: [[1,1,1],[1,1,1],[1,1,1]] -> 1 province
// Fully disconnected 3x3: [[1,0,0],[0,1,0],[0,0,1]] -> 3 provinces
What should a senior engineer know?
- Dense vs sparse. The n^2 cost is a property of the dense matrix input, not of Union-Find itself. With an edge list, Union-Find runs in O(E * alpha(n)).
- Incremental connectivity. Union-Find supports adding edges one at a time and answering connectivity queries between any two nodes, which DFS does not support without a full re-run.
- Weighted Union-Find. For more complex problems (like network flow or minimum spanning tree), Union-Find can carry weights on edges.
- Real network monitoring. In production, connectivity changes dynamically as links go up and down. Union-Find can be rebuilt periodically, or an online algorithm can process edge additions.
Visual Overview
Matrix:
┌───────────┐
│ 1 1 0 │ City 0 connected to City 1
│ 1 1 0 │
│ 0 0 1 │ City 2 alone
└───────────┘
Union-Find steps:
Start: count=3 {0} {1} {2}
Scan upper triangle:
(0,1): m[0][1]=1 -> union(0,1) -> success -> count=2
(0,2): m[0][2]=0 -> skip
(1,2): m[1][2]=0 -> skip
Result: count=2
Province 1: {0, 1}
Province 2: {2}
Key Takeaway
Number of Provinces is Union-Find applied to a symmetric adjacency matrix. I start a province counter at n, because each city begins in its own group, and then scan the upper triangle of the matrix. For every pair marked as directly connected, I union them, and each successful union decrements the counter. When the scan completes, the counter holds the number of connected components.
The cost is O(n^2) because the dense matrix must be fully scanned, with each union operation costing nearly constant time thanks to path compression and union by rank. The DFS alternative runs DFS from each unvisited city and counts the number of calls, achieving the same O(n^2) time.
At the National Bank of India, regional data hubs were described by a connectivity matrix, and the network team needed the number of independent provinces so each province could get its own failover plan. Union-Find gave a clean count, and because a direct line between two hubs already in the same province never created a spurious new group, the failover plans stayed exactly right.
Remember one sentence: start at n, union every connected pair, and the leftover count is the number of provinces.
---