CPP Program Strongly Connected Components – Advanced Graphs

KosaRaju’s Algorithm:

Strongly Connected Components Problem.

Code:

#include <iostream>
#include <vector>
#include <stack>
#include <iterator>
#include <unordered_set>
using namespace std;
void dfs(vector<int> *edges, unordered_set<int> &visited, stack<int> &finished_vertices, int start)
{
    visited.insert(start);
    for (int i = 0; i < edges[start].size(); i++)
    {
        int adjacent_element = edges[start][i];
        if (visited.count(adjacent_element) == 0)
        {
            dfs(edges, visited, finished_vertices, adjacent_element);
        }
    }
    finished_vertices.push(start);
}
void dfs2(vector<int> *edgesT, int start, unordered_set<int> &visited, unordered_set<int> *component)
{
    visited.insert(start);
    component->insert(start);
    for (int i = 0; i < edgesT[start].size(); i++)
    {
        int adjacent = edgesT[start][i];
        if (visited.count(adjacent) == 0)
        {
            dfs2(edgesT, adjacent, visited, component);
        }
    }
}
unordered_set<unordered_set<int> *> *getSCC(vector<int> *edges, vector<int> *edgesT, int n)
{
    unordered_set<int> visited;
    stack<int> finished_vertices;
    for (int i = 0; i < n; i++)
    {
        if (visited.count(i) == 0)
        {
            dfs(edges, visited, finished_vertices, i);
        }
    }
    unordered_set<unordered_set<int> *> *output = new unordered_set<unordered_set<int> *>();
    visited.clear();
    while (!finished_vertices.empty())
    {
        int element = finished_vertices.top();
        finished_vertices.pop();
        if (visited.count(element) != 0)
        {
            continue;
        }
        unordered_set<int> *component = new unordered_set<int>();
        dfs2(edgesT, element, visited, component);
        output->insert(component);
    }
    return output;
}
int main()
{
    int n; //number of vertices
    cin >> n;
    vector<int> *edges = new vector<int>[n];
    vector<int> *edgesT = new vector<int>[n];
    int m; //number of eges
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        int j, k;
        cin >> j >> k;
        edges[j - 1].push_back(k - 1);
        edgesT[k - 1].push_back(j - 1);
    }
    unordered_set<unordered_set<int> *> *components = getSCC(edges, edgesT, n);

    unordered_set<unordered_set<int> *>::iterator it1 = components->begin();
    while (it1 != components->end())
    {
        unordered_set<int> *component = *it1;
        unordered_set<int>::iterator it2 = component->begin();
        while (it2 != component->end())
        {
            cout << *it2 + 1 << " ";
            it2++;
        }
        cout << endl;
        delete component;
        it1++;
    }

    delete components;
    delete[] edges;
    delete[] edgesT;
}
Code language: C++ (cpp)

Leave a Comment