icpc/scc.hpp

• View this file on GitHub
• Last update: 2023-05-31 02:53:46+09:00
• Include: #include "icpc/scc.hpp"
• Link: https://onlinejudge.u-aizu.ac.jp/problems/2748

Depends on

• icpc/template.hpp

Verified with

• verify/aoj_other/aoj_2748.test.cpp

Code

#pragma once

#include "icpc/template.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/2748

V<V<int>> scc(V<V<int>>& g) {
    int n = int(g.size());
    int now_ord = 0, group_num = 0;
    V<int> vis, low(n), ord(n, -1), ids(n);
    vis.reserve(n);
    auto dfs = [&](auto f, int c) -> void {
        low[c] = ord[c] = now_ord++;
        vis.push_back(c);
        for (auto& e : g[c]) {
            if (ord[e] == -1) {
                f(f, e);
                low[c] = min(low[c], low[e]);
            } else {
                low[c] = min(low[c], ord[e]);
            }
        }
        if (low[c] == ord[c]) {
            while (true) {
                int u = vis.back();
                vis.pop_back();
                ord[u] = n;
                ids[u] = group_num;
                if (u == c) break;
            }
            group_num++;
        }
    };
    REP(i, n) if (ord[i] == -1) dfs(dfs, i);
    V<V<int>> res(group_num);
    REP(i, n) res[group_num - 1 - ids[i]].push_back(i);
    return res;
}

#line 2 "icpc/scc.hpp"

#line 2 "icpc/template.hpp"

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

using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[ ";
    for (auto& vi : v) os << vi << ", ";
    return os << "]";
}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif

using uint = unsigned int;
using ull = unsigned long long;

// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 4 "icpc/scc.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/2748

V<V<int>> scc(V<V<int>>& g) {
    int n = int(g.size());
    int now_ord = 0, group_num = 0;
    V<int> vis, low(n), ord(n, -1), ids(n);
    vis.reserve(n);
    auto dfs = [&](auto f, int c) -> void {
        low[c] = ord[c] = now_ord++;
        vis.push_back(c);
        for (auto& e : g[c]) {
            if (ord[e] == -1) {
                f(f, e);
                low[c] = min(low[c], low[e]);
            } else {
                low[c] = min(low[c], ord[e]);
            }
        }
        if (low[c] == ord[c]) {
            while (true) {
                int u = vis.back();
                vis.pop_back();
                ord[u] = n;
                ids[u] = group_num;
                if (u == c) break;
            }
            group_num++;
        }
    };
    REP(i, n) if (ord[i] == -1) dfs(dfs, i);
    V<V<int>> res(group_num);
    REP(i, n) res[group_num - 1 - ids[i]].push_back(i);
    return res;
}

Back to top page