The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# 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.

#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:**
* From lines 1 to 3, we import all the header files required.
* On line 5, we define a `template class` in C++. 
* On line 8, we define our adjacency list.
* On line 10, we define our constructor for the class.
* On line 13, we define a function `addEdge()` which will accept the two vertices that need to be joined by an edge and also a boolean value that will determine whether the edge is directional or bidirectional.
* On line 15, we add the vertex `v` to the list of `u`.
* If the edge is bidirectional then on line 17, we add the vertex `u` to the list of `v`.
* On line 20, we define our function `dfsHelper()` which will accept the `node` and the `visited` map (*by reference*).
* On lines 22 and 23, we mark the current node as visited (*store the node with a boolean value as `True`.*) and then print that node.
* From lines 25 to 28, we run a loop while picking one neighbor of the current node and checking whether it has been visited or not. If not, we call the function recursively (*remember that we discussed that stack can be used to implement DFS*) by passing the `neighbor` node with the `visited` map.
* On line 32, we define the function `dfs()` which will accept the source node.
* On line 35, we initialize the number of components as `1`. (*There will be atleast 1 component.*)
* On line 36, we call the `dfsHelper()` function by passing the source node. This will mark all the nodes which are in the single-component as visited.
* From lines 38 to 46, we check each node to see if it has been visited or not. If not, we again call the `dfsHelper()` function that will mark the remaining nodes as visited and increment the number of components. (*This process will continue till all the nodes are visited*). 
* On line 47, we finally print the number of components.
* In the `main()` function, we create the object of the class `Graph` and use it to create the graph (add vertex and edges). Finally, we call our `dfs()` function by passing the source node.

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

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Find the Number of Connected Components in a Graph

Problem statement