Number of Provinces (Connected Components in Graphs)

Finding the number of provinces in a graph is a foundational problem in graph theory. It introduces the concept of Connected Components—isolated islands of nodes where every node in a component can reach every other node, but no path exists between different components.

1. Why Do We Need This? (Problem Statement & Status Quo)

The Problem

You are given an undirected graph with $V$ vertices. Two vertices $u$ and $v$ belong to a single province if there is a path from $u$ to $v$ (or equivalently, from $v$ to $u$). Your task is to find the total number of provinces in the graph.

The Real-World Scenario

Imagine a network of cities where roads connect certain pairs of cities.

• A province is a cluster of cities connected directly or indirectly by roads.
• If City A connects to City B, and City B connects to City C, then Cities A, B, and C all belong to the same province.
• If there are no roads bridging City C to City D, then City D belongs to an entirely separate province.
• The goal is to count how many completely isolated road networks exist in the country.

2. Core Mental Model: Islands and Traversals

Real-Life Analogy

Think of a group of islands. Bridges connect islands within the same group, but no bridges span across different groups.

• If you drop a tourist onto Island 1, they can explore every island connected to it via bridges. Once they have visited all of them, they have explored Province #1.
• To find all provinces, you must look around the map. If you spot an unvisited island in a completely separate group, you drop a second tourist there to explore Province #2, and so on, until every island has been visited.

3. Naive vs. Optimal Approach

• Naive Approach (Brute Force): Try all-pairs shortest paths using algorithms like Floyd-Warshall ($O(V^3)$ time complexity), which is massively overkill and inefficient for large graphs.
• Optimal Approach (DFS / BFS with a Visited Array): Iterate through all nodes from $1$ to $V$. Whenever you encounter an unvisited node, trigger a traversal (DFS or BFS) to explore its entire connected component, and increment a counter.

4. Step-by-Step Algorithm Evolution

To implement this efficiently, we follow three core steps:

1. Graph Representation: Convert the input (often given as an adjacency matrix) into an adjacency list for clean traversal.
2. Visited Tracking: Create a boolean/integer visited array of size $V + 1$ initialized to $0$ (false) to keep track of nodes we have already explored.
3. Outer Loop + Counter: Run a loop from node $1$ to $V$. If a node is unvisited, launch a DFS/BFS from it (which sweeps through the entire connected component) and increment our province counter.

5. Input Format Challenge: Adjacency Matrix to Adjacency List

Problems in interviews or online judges sometimes provide graphs as an adjacency matrix (a 2D grid where matrix[i][j] == 1 indicates an edge). We can quickly convert this into an adjacency list.

// Converting Adjacency Matrix to Adjacency List in C++
vector<vector<int>> adjLs(V);
for(int i = 0; i < V; i++) {
    for(int j = 0; j < V; j++) {
        // If there is an edge and it's not a self-loop
        if(adjMatrix[i][j] == 1 && i != j) {
            adjLs[i].push_back(j);
            adjLs[j].push_back(i);
        }
    }
}

6. Complete Flow Walkthrough

Let's trace how the algorithm processes a graph with 8 nodes divided into 3 provinces:

• Province A: Nodes [1, 2, 3]
• Province B: Nodes [4, 5, 6]
• Province C: Nodes [7, 8]

7. Complete Code Implementation (Java & C++)

Java Implementation

import java.util.ArrayList;

class Solution {
    private static void dfs(int node, ArrayList<ArrayList<Integer>> adjLs, int[] vis) {
        vis[node] = 1;
        for(Integer it : adjLs.get(node)) {
            if(vis[it] == 0) {
                dfs(it, adjLs, vis);
            }
        }
    }

    static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {
        ArrayList<ArrayList<Integer>> adjLs = new ArrayList<ArrayList<Integer>>();
        for(int i = 0; i < V; i++) {
            adjLs.add(new ArrayList<Integer>());
        }
        
        // Convert adjacency matrix to adjacency list
        for(int i = 0; i < V; i++) {
            for(int j = 0; j < V; j++) {
                if(adj.get(i).get(j) == 1 && i != j) {
                    adjLs.get(i).add(j);
                    adjLs.get(j).add(i);
                }
            }
        }
        
        int[] vis = new int[V];
        int count = 0;
        for(int i = 0; i < V; i++) {
            if(vis[i] == 0) {
                count++;
                dfs(i, adjLs, vis);
            }
        }
        return count;
    }
}

C++ Implementation

class Solution {
private:
    void dfs(int node, vector<vector<int>>& adjLs, vector<int>& vis) {
        vis[node] = 1;
        for(auto it : adjLs[node]) {
            if(!vis[it]) {
                dfs(it, adjLs, vis);
            }
        }
    }
public:
    int findCircleNum(vector<vector<int>>& adj) {
        int V = adj.size();
        vector<vector<int>> adjLs(V);
        
        // Convert adjacency matrix to adjacency list
        for(int i = 0; i < V; i++) {
            for(int j = 0; j < V; j++) {
                if(adj[i][j] == 1 && i != j) {
                    adjLs[i].push_back(j);
                    adjLs.id[j].push_back(i); // Note: standard push_back
                }
            }
        }
        
        vector<int> vis(V, 0);
        int count = 0;
        for(int i = 0; i < V; i++) {
            if(!vis[i]) {
                count++;
                dfs(i, adjLs, vis);
            }
        }
        return count;
    }
};

8. Complexity Analysis

Space Complexity

• Visited Array (vis): Takes $O(V)$ auxiliary space to keep track of visited nodes.
• Recursion Stack Space: In the worst-case scenario (a completely linear graph or skewed graph like a straight line), the DFS recursion stack can grow up to $O(V)$ depth.
• Total Space Complexity: $O(V)$ (excluding the space required for the adjacency list itself).

Time Complexity

• Outer Loop: Iterates through all $V$ vertices taking $O(V)$ time.
• DFS Traversals: Although a DFS is called multiple times from the outer loop, across the entire execution of the algorithm, every node is visited exactly once, and every edge is traversed twice (once from each endpoint).
• Total Time Complexity: $O(V + 2E)$, where $V$ is the number of vertices and $E$ is the number of edges. This simplifies to linear time relative to the size of the graph.

Summary and Key Takeaways

• Definition of a Province: A connected component in an undirected graph where paths exist between any two nodes within the same component.
• Traversal Independence: Both Depth-First Search (DFS) and Breadth-First Search (BFS) can be used interchangeably to explore connected components.
• The Visited Array Guard: The outer loop checks if (!vis[i]) to ensure we only trigger a traversal for unvisited nodes, which directly maps to counting the number of provinces.
• Matrix-to-List Conversion: When given an adjacency matrix, converting it to an adjacency list beforehand keeps our traversal logic clean and efficient.
• Linear Complexity: The algorithm operates in $O(V + 2E)$ time because traversals never revisit already marked nodes.
• Recursive Stack Considerations: Keep the maximum recursion depth in mind for extremely large, skewed graphs to avoid stack overflow errors.