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\n1 2\n2 3\n3 1\n4 5\n5 4

Output:
2\n1 2 3\n4 5

Solution in C++


#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int timeCounter = 0;

void tarjanDFS(int u, const vector<vector<int>> &adj, vector<int> &disc, vector<int> &low, stack<int> &st, vector<bool> &inStack, vector<vector<int>> &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<int> 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<vector<int>> adj(n);
    for(int i=0;i<m;i++){
        int u, v; cin >> u >> v; u--; v--;
        adj[u].push_back(v);
    }
    vector<int> disc(n, -1), low(n, -1);
    vector<bool> inStack(n, false);
    stack<int> st;
    vector<vector<int>> scc;
    for(int i=0;i<n;i++){
        if(disc[i] == -1)
            tarjanDFS(i, adj, disc, low, st, inStack, scc);
    }
    cout << scc.size() << "\n";
    for(auto &comp : scc){
        for(auto v : comp) cout << v+1 << " ";
        cout << "\n";
    }
    return 0;
}