test/yosupo/graph/scc_csr.test.cpp

View this file on GitHub
Last update: 2025-09-20 17:47:50+07:00
Problem: https://judge.yosupo.jp/problem/scc

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"

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

#include "graph/csr.hpp"
#include "graph/scc.hpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> es(m);
    for (auto &[u, v] : es) cin >> u >> v;
    CSR<int> g(n, move(es));

    auto scc = find_scc(g);

    cout << scc.size() << "\n";
    for (auto comp : move(scc)) {
        cout << comp.size();
        for (int v : comp) cout << " " << v;
        cout << "\n";
    }
}

#line 1 "test/yosupo/graph/scc_csr.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"

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

#line 2 "graph/csr.hpp"

template<class E> struct CSR {
    CSR() {}
    CSR(int _n, const vector<pair<int, E>> &_edges) :
        n(_n), start(n + 1), edges((int)_edges.size()) {
        for (auto &[from, _] : _edges) start[from + 1]++;
        for (int i = 1; i <= n; i++) start[i] += start[i - 1];
        auto cnt = start;
        for (auto &[from, e] : _edges) edges[cnt[from]++] = e;
    }

    int size() const { return n; }

    struct range {
        E *edges;
        const int first, last;
        struct iterator {
            E *elist;
            int p;
            bool operator!=(const iterator &r) const { return p != r.p; }
            void operator++() { p++; }
            E &operator*() { return elist[p]; }
        };
        E &operator[](size_t i) {
            assert(i < size());
            return edges[first + i];
        }
        E &back() { return edges[last - 1]; }
        iterator begin() { return {edges, first}; }
        iterator end() { return {edges, last}; }
        int size() const { return last - first; }
        bool empty() const { return first == last; }
    };
    struct const_range {
        const E *edges;
        const int first, last;
        struct iterator {
            const E *elist;
            int p;
            bool operator!=(const iterator &r) const { return p != r.p; }
            void operator++() { p++; }
            const E &operator*() const { return elist[p]; }
        };
        const E &operator[](size_t i) const {
            assert(i < size());
            return edges[first + i];
        }
        const E &back() const { return edges[last - 1]; }
        iterator begin() const { return {edges, first}; }
        iterator end() const { return {edges, last}; }
        int size() const { return last - first; }
        bool empty() const { return first == last; }
    };
    range operator[](size_t i) {
        assert(i < size());
        return {edges.data(), start[i], start[i + 1]};
    }
    const_range operator[](size_t i) const {
        assert(i < size());
        return {edges.data(), start[i], start[i + 1]};
    }

    struct iterator {
        CSR *g;
        int p;
        bool operator!=(const iterator &r) const { return p != r.p; }
        void operator++() { p++; }
        range operator*() { return (*g)[p]; }
    };
    struct const_iterator {
        const CSR *g;
        int p;
        bool operator!=(const const_iterator &r) const { return p != r.p; }
        void operator++() { p++; }
        const_range operator*() const { return (*g)[p]; }
    };
    iterator begin() { return {this, 0}; }
    iterator end() { return {this, n}; }
    const_iterator begin() const { return {this, 0}; }
    const_iterator end() const { return {this, n}; }

  private:
    int n;
    vector<int> start;
    vector<E> edges;
};
#line 2 "graph/scc.hpp"

template<class G> auto find_scc(const G &g) {
    int n = (int)g.size();
    vector<int> val(n), z;
    vector<char> added(n);
    vector<basic_string<int>> scc;
    int time = 0;
    auto dfs = [&](auto &self, int v) -> int {
        int low = val[v] = time++;
        z.push_back(v);
        for (auto u : g[v])
            if (!added[u]) low = min(low, val[u] ?: self(self, u));
        if (low == val[v]) {
            scc.emplace_back();
            int x;
            do {
                x = z.back(), z.pop_back();
                added[x] = true;
                scc.back().push_back(x);
            } while (x != v);
        }
        return val[v] = low;
    };
    for (int i = 0; i < n; i++)
        if (!added[i]) dfs(dfs, i);
    reverse(begin(scc), end(scc));
    return scc;
}
template<class G> auto condense(const G &g) {
    auto scc = find_scc(g);
    int n = (int)scc.size();
    vector<int> rep(g.size());
    for (int i = 0; i < n; i++)
        for (auto v : scc[i]) rep[v] = i;
    vector<basic_string<int>> gd(n);
    for (int v = 0; v < g.size(); v++)
        for (auto u : g[v])
            if (rep[v] != rep[u]) gd[rep[v]].push_back(rep[u]);
    for (auto &v : gd) {
        sort(begin(v), end(v));
        v.erase(unique(begin(v), end(v)), end(v));
    }
    return make_tuple(move(scc), move(rep), move(gd));
}
#line 8 "test/yosupo/graph/scc_csr.test.cpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> es(m);
    for (auto &[u, v] : es) cin >> u >> v;
    CSR<int> g(n, move(es));

    auto scc = find_scc(g);

    cout << scc.size() << "\n";
    for (auto comp : move(scc)) {
        cout << comp.size();
        for (int v : comp) cout << " " << v;
        cout << "\n";
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	6 ms	4 MB
g++	large_cycle_00	AC	139 ms	63 MB
g++	max_random_00	AC	138 ms	34 MB
g++	max_random_01	AC	135 ms	34 MB
g++	max_random_02	AC	135 ms	34 MB
g++	max_random_03	AC	136 ms	34 MB
g++	max_random_04	AC	146 ms	34 MB
g++	random_00	AC	120 ms	31 MB
g++	random_01	AC	126 ms	31 MB
g++	random_02	AC	54 ms	14 MB
g++	random_03	AC	65 ms	26 MB
g++	random_04	AC	57 ms	25 MB
clang++	example_00	AC	5 ms	4 MB
clang++	large_cycle_00	AC	114 ms	51 MB
clang++	max_random_00	AC	142 ms	34 MB
clang++	max_random_01	AC	149 ms	34 MB
clang++	max_random_02	AC	141 ms	34 MB
clang++	max_random_03	AC	144 ms	34 MB
clang++	max_random_04	AC	149 ms	34 MB
clang++	random_00	AC	114 ms	30 MB
clang++	random_01	AC	124 ms	32 MB
clang++	random_02	AC	53 ms	13 MB
clang++	random_03	AC	72 ms	26 MB
clang++	random_04	AC	62 ms	23 MB