verify/Graph_scc_old.test.cpp

View this file on GitHub
Last update: 2025-01-11 19:51:13+09:00
Problem: https://judge.yosupo.jp/problem/scc

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include "../Utility/template.hpp"
#include "../Graph/scc_old.hpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> g(n);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    auto res = SCC::groups(g);
    
    cout << res.size() << endl;

    rep(i, 0, res.size()) {
        cout << res[i].size() << " ";
        for(auto v : res[i]) cout << v << " ";
        cout << endl;
    }
}

#line 1 "verify/Graph_scc_old.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Graph/scc_old.hpp"
namespace SCC {
vec<int> ids(const vec<vec<int>> &g) {
    using vi = vec<int>;
    using vvi = vec<vi>;

    int n = g.size();
    vvi rg(n);
    vi vs, cmp(n, -1);
    vec<bool> seen(n, false), nees(n, false);

    rep(i, 0, n) for (int to : g[i]) rg[to].push_back(i);

    auto dfs = [&](auto f, int v) -> void {
        seen[v] = true;
        for (auto to : g[v])
            if (!seen[to]) f(f, to);
        vs.push_back(v);
        return;
    };

    int k = 0;

    auto sfd = [&](auto f, int v) -> void {
        nees[v] = true;
        cmp[v] = k;
        for (int to : rg[v])
            if (!nees[to]) f(f, to);
        return;
    };

    rep(i, 0, n) if (!seen[i]) dfs(dfs, i);
    rrep(i, 0, vs.size()) if (!nees[vs[i]]) sfd(sfd, vs[i]), k++;
    return cmp;
}

vec<vec<int>> groups(const vec<vec<int>> &g) {
    int n = g.size();
    vec<int> id = ids(g);

    vec<vec<int>> gs(n);
    rep(i, 0, n) gs[id[i]].push_back(i);
    while (gs.empty() == false && gs.back().empty() == true) {
        gs.pop_back();
    }
    return gs;
}

vec<vec<int>> graph(const vec<vec<int>> &g) {
    vec<int> id = ids(g);
    int n = 0;
    rep(i, 0, g.size()) chmax(n, id[i] + 1);

    vec<vec<int>> ng(n);
    rep(i, 0, g.size()) for (int to : g[i]) {
        if (id[i] == id[to]) continue;
        ng[id[i]].push_back(id[to]);
    }
    return ng;
}

vec<vec<int>> graph_rev(const vec<vec<int>> &g) {
    auto ser = graph(g);
    int n = ser.size();
    vec<vec<int>> res(n);
    rep(i, 0, n) for(int to : ser[i]) {
        res[to].push_back(i);
    }
    return res;
}

}  // namespace SCC

/*
@brief scc_old
@docs doc/scc.md
*/
#line 4 "verify/Graph_scc_old.test.cpp"

int main() {
    int n, m;
    cin >> n >> m;
    vec<vec<int>> g(n);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
    }

    auto res = SCC::groups(g);
    
    cout << res.size() << endl;

    rep(i, 0, res.size()) {
        cout << res[i].size() << " ";
        for(auto v : res[i]) cout << v << " ";
        cout << endl;
    }
}