tanjan

/* tanjan */
#include <vector>
#include <stack>

constexpr int _MAXV = 1e5;

vector<int> _G[_MAXV + 1];
stack<int> _st;
int _cnt, _dfn[_MAXV + 1]{}, _low[_MAXV + 1]{};
bool _instack[_MAXV + 1]{};

void _tanjan(int now)
{
    if (_dfn[now]) return;

    _dfn[now] = _low[now] = ++_cnt;
    _st.emplace(now);
    _instack[now] = true;

    for (auto nex : _G[now])
    {
        if (!_dfn[nex])
        {
            _tanjan(nex);
            _low[now] = min(_low[now], _low[nex]);
        }
        else if (_instack[nex])
            _low[now] = min(_low[now], _dfn[nex]);
    }

    if (_low[now] == _dfn[now])
    {
        int node;
        do
        {
            node = _st.top(); _st.pop();
            _instack[node] = false;

        } while (node != now);
    }
}

void init() noexcept
{
    for (int i = 1; i <= n; ++i)
        _G[i].clear();

    _st = stack<int>();
    memset(_instack, false, _MAXV + 1);
    memset(_dfn, 0, sizeof(int) * (_MAXV + 1));
    _cnt = 0;
}