Competitive Programming - Crack Your Coding Interview, C++/

...

/

Find the Number of Connected Components in a Graph

Find the Number of Connected Components in a Graph

Take your understanding of Depth-First Search to the next level by finding the connected components in a graph.

We'll cover the following...

Problem statement

Find the connected components in an undirected graph.

In graph theory, a connected component (or just component) of an undirected graph is a sub-graph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the super-graph.

Solution

This problem can be solved using Depth-First Search. Let’s move on to the implementation as the Depth First Approach must already be clear. Let’s look at the code.

C++
#include <iostream>
#include <map>
#include <list>
using namespace std;
template <typename T>
class Graph
{
    map<T, list<T>> adjList;
  public:
    Graph()
    {
    }
    void addEdge(T u, T v, bool bidir = true)
    {
        adjList[u].push_back(v);
        if (bidir)
            adjList[v].push_back(u);
    }
    void dfsHelper(T node, map<T, bool> &visited)
    {
        visited[node] = true;
        cout << node << " ";
        for (T neighbor : adjList[node])
        {
            if (!visited[neighbor])
            {
                dfsHelper(neighbor, visited);
            }
        }
    }
    void dfs(T source_node)
    {
        map<T, bool> visited;
        int component = 1;
        dfsHelper(source_node, visited);
        cout << endl;
        for (auto i : adjList)
        {
            T city = i.first;
            if (!visited[city])
            {
                dfsHelper(city, visited);
                component++;
            }
        }
        cout << "\nNumber of Components : " << component << endl;
    }
};
int main()
{
    Graph<string> g;
    g.addEdge("Amritsar", "Jaipur");
    g.addEdge("Amritsar", "Delhi");
    g.addEdge("Delhi", "Jaipur");
    g.addEdge("Mumbai", "Jaipur");
    g.addEdge("Mumbai", "Bhopal");
    g.addEdge("Delhi", "Bhopal");
    g.addEdge("Mumbai", "Bangalore");
    g.addEdge("Agra", "Delhi");
    g.addEdge("Andaman", "Nicobar");
    g.dfs("Amritsar");
    return 0;
}

Explanation: ...