Problem Statement

Given a undirected Graph consisting of V vertices numbered from 0 to V-1 and E edges. The ith edge is represented by [ai,bi], denoting a edge between vertex ai and bi. We say two vertices u and v belong to a same component if there is a path from u to v or v to u. Find the number of connected components in the graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

Examples

Example 1:

            -----
            | 1 |
            -----
          /       \
         /         \
     -----        -----   -----
     | 2 |        | 0 |   | 3 |
     -----        -----   -----

Input: V = 4
       edges = [
                 [0, 1],
                 [1, 2]
               ]
Output: 2

Explanation: Vertices [0, 1, 2] forms the first component and vertex 3
forms the second component.

Example 2:

            -----      -----   -----
            | 1 |------| 3 |   | 5 |
            -----      -----   -----
          /       \            /
         /         \          /
     -----        -----   -----     -----
     | 2 |        | 0 |   | 4 |     | 6 |
     -----        -----   -----     -----

Input: V = 7
       edges = [
                 [0, 1],
                 [1, 2],
                 [2, 3],
                 [4, 5]
               ]
Output: 3

Explanation: Vertices [0, 1, 2, 3] forms the first component and vertex [4, 5] forms the second component and the isolated vertices [6] forms the third component.

Different Approaches

1️⃣ Graph Traversal

Approach:

1. Convert the given adjacency matrix to adjacency list for easy traversal.
2. Initialise a visited array to mark the nodes that as visited and a counter to count the number of components found.
3. Every time a new node is visited, a new component is founds so increment the counter and traverse all the nodes connected to current node.
4. By the end of the exploration, the counter will get us the total number of components.

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 call to find the number of 
    connected components in the given graph */
    int findNumberOfComponent(int E, int V, 
                              vector<vector<int>> &edges) {
        
        // To store adjacency list
        vector<int> adjLs[V];
        
        // Add edges to adjacency list
        for(int i=0; i < E; i++) {
            adjLs[edges[i][0]].push_back(edges[i][1]);
            adjLs[edges[i][1]].push_back(edges[i][0]);
        }
        
        // Visited array
        int vis[V] = {0}; 
        
        // Variable to store number of components
        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 using any traversal */
                bfs(i, adjLs, vis); 
                //dfs(i, adjLs, vis);
            }
        }
        
        // Return the count
        return cnt; 
    }
};

int main() {
    int V = 4, E = 2;
    vector<vector<int>> edges = {
        {0, 1},
        {1, 2}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the number of 
    connected components in the given graph */
    int ans = sol.findNumberOfComponent(E, V, edges);
    
    cout << "The number of components 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 the edges to adjacency list takes O(E) time.
  • 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.