strongly_connected_components

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 1;

vector<int> adj[N], adj_t[N]; // adj_t is the transpose of adj
vector<int> order;            // stores nodes in order of finishing times
vector<bool> vis(N);          // visited array
vector<int> id(N);            // component id for each node
int component_count = 0;      // counts number of SCCs

// First DFS pass to fill the order vector
void dfs1(int v) {
    vis[v] = true;
    for (int u : adj[v]) {
        if (!vis[u]) {
            dfs1(u);
        }
    }
    order.push_back(v);
}

// Second DFS pass on the transpose graph
void dfs2(int v, int comp) {
    vis[v] = true;
    id[v] = comp;
    for (int u : adj_t[v]) {
        if (!vis[u]) {
            dfs2(u, comp);
        }
    }
}

int main() {
    int n, m; // n = number of nodes, m = number of edges
    cin >> n >> m;

    // Read edges and build both original and transpose graphs
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj_t[v].push_back(u);
    }

    // First DFS pass to get processing order
    fill(vis.begin(), vis.end(), false);
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs1(i);
        }
    }

    // Second DFS pass on transpose graph in reverse order
    fill(vis.begin(), vis.end(), false);
    reverse(order.begin(), order.end());
    for (int v : order) {
        if (!vis[v]) {
            dfs2(v, component_count++);
        }
    }

    // Output results
    cout << "Number of strongly connected components: " << component_count << endl;
    cout << "Component assignments:\n";
    for (int i = 1; i <= n; i++) {
        cout << "Node " << i << " is in component " << id[i] << endl;
    }

    return 0;
}