Problem Statement

You are given an undirected graph represented as an adjacency matrix isConnected where:

• isConnected[i][j] = 1 means that the i-th and j-th nodes are directly connected.
• isConnected[i][j] = 0 means that the i-th and j-th nodes are not directly connected.

A province is a group of directly or indirectly connected cities, and no city outside the group is connected to any city in the group.

Your task is to find the total number of provinces (i.e., connected components in the graph).

Input:

• An integer matrix isConnected of size n x n where n is the number of cities.

Output:

• An integer representing the number of provinces.

Examples

Example 1:

Input: adj = [
               [1, 1, 0],
               [1, 1, 0],
               [0, 0, 1]
             ]
Output: 2

Explanation: There are two provinces: one composed of cities 0 and 1, and one consisting of city 2.

Example 2:

Input: adj = [
               [1, 0, 0],
               [0, 1, 0],
               [0, 0, 1]
             ]
Output: 3

Explanation: Each city is its own province as there are no connections between them.

Different Approaches

1️⃣ Depth-First Search (DFS)

We can treat this problem as finding the number of connected components in an undirected graph. Each connected component is considered a province.

• Traverse the graph using DFS starting from each unvisited city.
• Mark all cities connected to the current city as visited.
• Each time a new DFS traversal starts, it represents the discovery of a new province.

Steps:

1. Initialize a visited array.
2. For each city, if it has not been visited, start a DFS to mark all connected cities.
3. Increment the province count when you start a new DFS.

Code:

#include <iostream>
#include <vector>
using namespace std;

void dfs(int city, vector<vector<int>>& isConnected, vector<bool>& visited) {
    visited[city] = true;
    
    for (int i = 0; i < isConnected.size(); i++) {
        if (isConnected[city][i] == 1 && !visited[i]) {
            dfs(i, isConnected, visited);
        }
    }
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    vector<bool> visited(n, false);
    int provinces = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, isConnected, visited);
            provinces++;
        }
    }
    
    return provinces;
}

int main() {
    vector<vector<int>> isConnected = {{1,1,0},{1,1,0},{0,0,1}};
    cout << "Number of Provinces: " << findCircleNum(isConnected) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n^2) where n is the number of cities, because in the worst case, we need to visit each city and check every connection between cities.
• Space Complexity:O(n) for the visited array, plus O(n) recursion stack space for DFS.

2️⃣ Breadth-First Search (BFS)

Instead of DFS, we can also use a queue to perform BFS for each unvisited city. BFS will traverse all cities connected to the starting city.

Code:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int city, vector<vector<int>>& isConnected, vector<bool>& visited) {
    queue<int> q;
    q.push(city);
    visited[city] = true;
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        
        for (int i = 0; i < isConnected.size(); i++) {
            if (isConnected[current][i] == 1 && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    vector<bool> visited(n, false);
    int provinces = 0;
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            bfs(i, isConnected, visited);
            provinces++;
        }
    }
    
    return provinces;
}

int main() {
    vector<vector<int>> isConnected = {{1,1,0},{1,1,0},{0,0,1}};
    cout << "Number of Provinces: " << findCircleNum(isConnected) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n^2) where n is the number of cities, as we still need to traverse each city and check all its connections.
• Space Complexity:O(n) for the visited array, and O(n) for the BFS queue.

3️⃣ By Converting Adjacency Matrix to Adjacency List

Approach

• Convert the given adjacency matrix to adjacency list for easy traversal.
• Initialize a visited array to mark the nodes that are visited and a counter to count the number of provinces found.
• Every time a new node is visited, a new province is founds so increment the counter and traverse all the nodes connected to current node.
• By the end of the exploration, the counter will get us the total number of provinces.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private: 
    // Function for BFS traversal
    void bfs(int node, vector<int> adjLs[], int vis[]) {
        
        // Mark the node as visited
        vis[node] = 1;
        
        // Queue required for BFS traversal
        queue <int> q;
        
        // To start traversal from node
        q.push(node); 
        
        /* Keep on traversing till 
        the queue is not empty */
        while(!q.empty()) {
            // Get the node
            int i = q.front();
            q.pop();
            
            // Traverse its unvisited neighbours
            for(auto adjNodes: adjLs[i]) {
                
                if(vis[adjNodes] != 1) {
                    
                    // Mark the node as visited
                    vis[adjNodes] = 1;
                    
                    // Add the node to queue
                    q.push(adjNodes);
                }
            }
        }
        
    }

    // Function for DFS traversal  
    void dfs(int node, vector<int> adjLs[], int vis[]) {
        
        // Mark the node as visited
        vis[node] = 1; 
        
        // Traverse its unvisited neighbours
        for(auto it: adjLs[node]) {
            
            if(!vis[it]) {
                // Recursively perform DFS
                dfs(it, adjLs, vis); 
            }
        }
    }
    
public:
    /* Function to find the number of
     provinces in the given graph */
    int numProvinces(vector<vector<int>> adj) {
        
        // Variable to store number of nodes
        int V = adj.size();
        
        // To store adjacency list
        vector<int> adjLs[V];
        
        // Convert adjacency matrix to adjacency list
        for(int i=0; i < V; i++) {
            for(int j=0; j < V; j++) {
                // self nodes are not considered
                if(adj[i][j] == 1 && i != j) {
                    adjLs[i].push_back(j); 
                    adjLs[j].push_back(i); 
                }
            }
        }
        
        // Visited array
        int vis[V] = {0}; 
        
        // Variable to store number of provinces
        int cnt = 0; 
        
        // Start Traversal
        for(int i=0; i < V; i++) {
            // If the node is not visited
            if(!vis[i]) {
                // Increment counter
                cnt++;
                
                // Start traversal from current node
                bfs(i, adjLs, vis); 
                //dfs(i, adjLs, vis);
            }
        }
        
        // Return the count
        return cnt; 
    }
};

int main() {
    vector<vector<int>> adj = 
    {
        {1, 0, 0, 1},
        {0, 1, 1, 0},
        {0, 1, 1, 0},
        {1, 0, 0, 1}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the 
    provinces in the given graph */
    int ans = sol.numProvinces(adj);
    
    cout << "The number of provinces in the given graph is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(V + E) (where V denotes the number of nodes, E denotes the number of edges).
  • Converting adjacency matrix to list takes O(V^2) time (equivalent to O(V + E).
  • Considering overall, all the nodes are visited through traversal techniques which takes O(V + E) time.
• Space Complexity: O(V + E)
  • Storing the adjacency list takes O(E) space.
  • Any traversal technique takes O(V) extra space.