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