1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24

namespace tarjan {
    int cnt, scc_num, scc[MN], in[MN], low[MN];
    stack<int> s;
    bitset<MN> ins;
    void tarjan(vector<int> * G, int u) {
        low[u] = in[u] = cnt++, ins[u] = 1; s.push(u);        
        for (int v : G[u]) {
            if (in[v] == -1) tarjan(G, v), low[u] = min(low[u], low[v]);
            else if (ins[v]) low[u] = min(low[u], in[v]);
        }
        if (low[u] == in[u]) {
            while (1) {
                int x = s.top(); s.pop();
                scc[x] = scc_num, ins[x] = 0;
                if (x == u) break;
            }
            ++scc_num;
        }
    }
    void find_scc(vector<int> * G) {
        memset(scc, -1, sizeof scc), memset(in, -1, sizeof in);
        for (int u = 1; u <= N; ++u) if (scc[u] == -1) tarjan(G, u);
    }
}