Problem 16: Tarjan's Strongly Connected Components
Problem Statement: Given a directed graph, find its strongly connected components using Tarjan's algorithm.
Input
First line contains n and m. Next m lines contain two integers u and v representing an edge from u to v.
Output
Output the number of strongly connected components followed by each component's vertices.
Examples
Input:
5 5
1 2
2 3
3 1
4 5
5 4
Output:
2
1 2 3
4 5
Solution Explanation
Method 1: Use Tarjan's algorithm by performing a single DFS and maintaining discovery and low-link values along with a stack to identify components. Method 2: Alternatively, apply Kosaraju's algorithm (which runs DFS twice) to find strongly connected components, though Tarjan's algorithm is more efficient in one pass.
Solution in C++
#include
#include
#include
#include
using namespace std;
int timeCounter = 0;
void tarjanDFS(int u, const vector> &adj, vector &disc, vector &low, stack &st, vector &inStack, vector> &scc){
disc[u] = low[u] = ++timeCounter;
st.push(u); inStack[u] = true;
for(int v : adj[u]){
if(disc[v] == -1){
tarjanDFS(v, adj, disc, low, st, inStack, scc);
low[u] = min(low[u], low[v]);
} else if(inStack[v]) {
low[u] = min(low[u], disc[v]);
}
}
if(low[u] == disc[u]){
vector component;
while(true){
int w = st.top(); st.pop(); inStack[w] = false;
component.push_back(w);
if(w == u) break;
}
scc.push_back(component);
}
}
int main(){
int n, m;
cin >> n >> m;
vector> adj(n);
for(int i=0;i> u >> v; u--; v--;
adj[u].push_back(v);
}
vector disc(n, -1), low(n, -1);
vector inStack(n, false);
stack st;
vector> scc;
for(int i=0;i