Kosaraju
Introduction:
This algorithm is simplest way of finding strongly connected components of a graph.
Problem Statement:
print the vertices of strongly connected components in a graph G.
Algorithm
1. mark all vertices as not visited
2. Do DFS for all non visited vertices while also storing the finished vertex into an array L.
3. create another graph \(G^T\) a transpose of given graph G.
4. do step 1 and do dfs on \(G^T\) for all unvisited vertices of L in reverse order .every time we call dfs we get a component,i.e., all those vertices reachable from u in L are in one connected component.
Code :
#include <bits/stdc++.h>
using namespace std;
vector<int> visited;
vector<int> ordered_list; // contains exit time of node in dfs
vector<vector<int>> scc;
vector<int> component;
void dfs(map<int, vector<int>> &adj, int s)
{
visited[s] = true;
// cout << s << " ";
for (auto u : adj[s])
{
if (!visited[u])
{
dfs(adj, u);
}
}
ordered_list.push_back(s);
}
void dfs_GT(map<int, vector<int>> &adj_GT, int s)
{
visited[s] = true;
component.push_back(s);
for (auto u : adj_GT[s])
{
if (!visited[u])
{
dfs_GT(adj_GT, u);
}
}
}
int main()
{
int num_edges;
cin >> num_edges;
map<int, vector<int>> adj;
// u - {v1, v2, .... vk}
// only directed edges
int u, v;
for (int i = 0; i < num_edges; i++)
{
cin >> u >> v;
adj[u].push_back(v);
}
int n = adj.size();
visited.assign(n, false);
for (int i = 0; i < n; i++)
{
if (!visited[i])
{
dfs(adj, i);
}
}
/// transpose
map<int, vector<int>> adj_GT;
for (auto u : adj)
{
for (auto v : u.second)
{
adj_GT[v].push_back(u.first);
}
}
visited.assign(n, false);
reverse(ordered_list.begin(), ordered_list.end());
for (auto u : ordered_list)
{
if (!visited[u])
{
dfs_GT(adj_GT, u);
scc.push_back(component);
component.clear();
}
}
for (auto connected_component : scc)
{
cout << "vertices in connected component: ";
for (auto v : connected_component)
{
cout << v << " ";
}
cout << "\n";
}
}
Complexity Analysis :
Time Complexity: \(O(|V|+|E|)\) because DFS is used.