Tarjan's Algorithm

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

const int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
int idx[MAXN], low[MAXN], comp[MAXN], timer_val;
bool inStack[MAXN];
stack<int> stk;
vector<vector<int>> sccs;
vector<pair<int,int>> bridges;
set<int> artPoints;

void dfs(int u, int par) {
    idx[u] = low[u] = timer_val++;
    stk.push(u); inStack[u] = true;
    int children = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        if (idx[v] == -1) {
            children++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] == idx[v])
                bridges.push_back({u, v});
            if (par != -1 && low[v] >= idx[u])
                artPoints.insert(u);
        } else if (inStack[v]) {
            low[u] = min(low[u], idx[v]);
        }
    }
    if (par == -1 && children > 1)
        artPoints.insert(u);
    if (low[u] == idx[u]) {
        sccs.push_back({});
        int v;
        do {
            v = stk.top(); stk.pop();
            inStack[v] = false;
            sccs.back().push_back(v);
            comp[v] = sccs.size() - 1;
        } while (v != u);
    }
}

void tarjan(int n) {
    memset(idx, -1, sizeof idx);
    timer_val = 0;
    for (int i = 0; i < n; i++)
        if (idx[i] == -1) dfs(i, -1);
}