// Finding the number of connected components in an undirected graph

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

void DFS(vector<vector<int>> &graph, int vertix);

// Run-Time: O(M+N) where M is the number of edges and N is the number of vertices
// Input:
// 1- Graph as an adjacency list (Vector used for simplicity)
vector<bool> visited;

bool strong_connectivity(vector<vector<int>> graph)
{

    // Checking if the Normal Graph DFS visits all nodes

    DFS(graph, 0);

    for (int i = 0; i < visited.size(); i++)
    {
        if (!visited.at(i))
        {
            return false;
        }
    }

    // Checking if the Reversed Graph DFS visits all nodes

    // Forming the Reverse Graph
    vector<vector<int>> reverse_graph;

    reverse_graph.resize(graph.size());
    for (int i = 0; i < graph.size(); i++)
    {
        int from = i;
        for (auto to : graph.at(from))
        {
            reverse_graph.at(to).push_back(from);
        }
    }

    for (int i = 0; i < visited.size(); i++)
    {
        visited.at(i) = false;
    }
    DFS(reverse_graph, 0);
    for (int i = 0; i < visited.size(); i++)
    {
        if (!visited.at(i))
        {
            return false;
        }
    }

    return true;
}

void DFS(vector<vector<int>> &graph, int vertix)
{

    visited.at(vertix) = true;

    for (int i = 0; i < graph.at(vertix).size(); i++)
    {

        if (!visited.at(graph.at(vertix).at(i)))
        {
            DFS(graph, graph.at(vertix).at(i));
        }
    }
}

// Example Run
int main()
{

    //  Sample Adjecency List
    vector<vector<int>> graph = {
        {1},
        {2},
        {3, 4},
        {0},
        {2}};
    // Visited Initilization
    visited.resize(graph.size(), false);

    // Sample Run
    cout << "Strongly Connected: " << strong_connectivity(graph) << endl;
}