Graph - DSA: Number of Provinces - Disjoint Set

1. Problem Statement & Objectives

The Number of Provinces problem asks us to find the total number of connected components in an undirected graph given with $V$ vertices.

Definition of a Province: Two vertices $u$ and $v$ belong to a single province if there is a path from $u$ to $v$ (or $v$ to $u$ ) by any means.
Input Format: The graph is represented as an Adjacency Matrix of size $V \times V$ , where a value of 1 at matrix[i][j] signifies an edge between vertex $i$ and vertex $j$ , and 0 indicates no direct edge.
Goal: While this can be solved using traditional traversal techniques like Breadth-First Search (BFS) or Depth-First Search (DFS), our primary objective here is to solve it using the Disjoint Set (DS) data structure. Mastering DS on simpler problems builds the foundational intuition required for solving advanced graph algorithms.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Corporate Organization and Bosses

Imagine a large corporation with multiple departments. Within each department, employees form a communication network, and every department ultimately reports to a single head or Boss (the ultimate parent).

If you check any employee's ultimate reporting chain, you will eventually trace it up to that department's boss.
Employees who are themselves bosses represent the distinct departments of the company.
By simply counting how many people act as their own boss (i.e., root nodes where ultimate_parent(x) == x), we can immediately determine the exact number of independent departments (provinces) in the corporation.

3. Disjoint Set Recap & Component Merging

Before writing the solution, recall that a Disjoint Set data structure (implemented via Union by Rank or Union by Size with Path Compression) groups elements into disjoint trees.

When we process connections between vertices:

If vertex 1 connects to 2, and 2 connects to 3, they form a single tree where 1 (or another node depending on rank/size) is the root/boss.
If vertex 4 connects to 5, they form a second tree with 4 as the boss.
If vertex 6 connects to 7, they form a third tree with 6 as the boss.

CODE

Tree 1:          Tree 2:          Tree 3:
   1                4                6
  / \               |                |
 2   3              5                7
(Boss: 1)        (Boss: 4)        (Boss: 6)

Each connected component collapses into a tree structure governed by a single ultimate parent (boss).

4. Naive Traversal vs. Disjoint Set Approach

Aspect	Traversal (BFS / DFS)	Disjoint Set (DSU)
Core Mechanism	Explores neighbors recursively or iteratively, marking visited nodes.	Dynamically unions connected nodes and tracks roots.
Time Complexity	$O(V + E)$ where $V$ is vertices and $E$ is edges.	$O(V^2 \alpha(V))$ due to adjacency matrix scanning and near-constant time DSU operations.
Space Complexity	$O(V)$ for visited array and recursion stack.	$O(V)$ for parent/size arrays.
Extensibility	Good for pure connectivity checks.	Excellent for dynamic edge additions and Kruskal's algorithm workflows.

5. Step-by-Step Algorithm Breakdown

Initialize DSU: Create a Disjoint Set data structure of size $V$ , where each node is initially its own parent.
Iterate Through Adjacency Matrix: Traverse the matrix using a nested loop (i from 0 to V-1, j from 0 to V-1).
Union Connected Nodes: If matrix[i][j] == 1 and $i \neq j$ , perform unionBySize(i, j) (or unionByRank).
Count Bosses: Once all edges are processed, iterate through all nodes from 0 to V-1. Check how many nodes satisfy the condition ds.findUltimateParent(i) == i.
Return Count: The total number of nodes that are their own ultimate parent equals the number of provinces.

6. Code Implementation (C++ & Java Equivalents)

C++ Solution Implementation

C++

class DisjointSet {
    vector<int> rank, parent, size;
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int findUltimateParent(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUltimateParent(parent[node]); // Path compression
    }

    void unionByRank(int u, int v) {
        int ulp_u = findUltimateParent(u);
        int ulp_v = findUltimateParent(v);
        if (ulp_u == ulp_v) return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        } else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        } else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    void unionBySize(int u, int v) {
        int ulp_u = findUltimateParent(u);
        int ulp_v = findUltimateParent(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        } else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int V = isConnected.size();
        DisjointSet ds(V);

        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (isConnected[i][j] == 1 && i != j) {
                    ds.unionBySize(i, j);
                }
            }
        }

        int count = 0;
        for (int i = 0; i < V; i++) {
            if (ds.findUltimateParent(i) == i) {
                count++;
            }
        }
        return count;
    }
};

7. Complete Flow Walkthrough

Consider a graph with 3 vertices and an adjacency matrix: