Find strongly connected component (SCC) with dfs tree

scc.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class DFSTree {
    vector<ll> nums, low;
    vector<bool> deleted;
    stack<ll> st;
    vector<ll> scc;
    ll time = 1, sccCnt = 0;

    void dfs(vector<vector<ll>>& graph, ll u, ll p) {
        nums[u] = low[u] = time++;
        st.push(u);

        for (ll i : graph[u]) {
            if (deleted[i]) {
                continue;
            }

            if (nums[i]) {
                low[u] = min(low[u], nums[i]);
                continue;
            }

            dfs(graph, i, u);

            low[u] = min(low[u], low[i]);
        }

        if (low[u] == nums[u]) {
            sccCnt++;
            ll v;

            do {
                v = st.top();
                st.pop();
                deleted[v] = true;
                scc[v] = sccCnt;
            } while (v != u);
        }
    }

   public:
    DFSTree(vector<vector<ll>>& graph) {
        nums = low = scc = vector<ll>(graph.size());
        deleted = vector<bool>(graph.size());

        for (ll i = 1; i < graph.size(); i++) {
            if (nums[i]) {
                continue;
            }

            dfs(graph, i, 0);
        }
    }

    ll SCC() {
        return sccCnt;
    }
};

int main() {
    ll n, m;
    cin >> n >> m;

    vector<vector<ll>> graph(n + 1);

    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;

        graph[a].push_back(b);
    }

    DFSTree a(graph);

    cout << a.SCC();
}