noginonoka / codeshelf Goto Github PK

int dfn[MAXN], low[MAXN], belong[MAXN];
bool trav[MAXN];    //used in disconnected graph
bool vis[MAXN];
vector<int> edges[MAXN];
stack<int> s;
int cnt = 0;

void dfs(int pos, int pre) {
    static int ts = 0;   //time stamp
    vis[pos] = true;
    trav[pos] = true;   //without reset later
    s.emplace(pos);
    low[pos] = dfn[pos] = ++ts;
    for (auto &nex : edges[pos]) {
        if (dfn[nex] == 0) {
            dfs(nex, pos);
            low[pos] = min(low[pos], low[nex]);
        } else {
            if (vis[nex]) {   //&& nex != pre) {    //in undirected graph, add this
                low[pos] = min(low[pos], dfn[nex]);
            }
        }
    }
    if (low[pos] == dfn[pos] && vis[pos]) {
        ++cnt;
        while (!s.empty() && s.top() != pos) {
            belong[s.top()] = cnt;
            vis[s.top()] = false;
            s.pop();
        }
        if (!s.empty()) s.pop();
        belong[pos] = cnt; vis[pos] = false;
    }
}

//in main, to traverse a disconnected graph
for (int i = 1; i <= n; i++) {
    if (!trav[i]) dfs(i, i);
}