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