test/yosupo/graph/scc_ael.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/ael.hpp"
#include "graph/scc.hpp"

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

    AEL<int> g(n);
    for (int u, v; m--;) {
        cin >> u >> v;
        g.add_edge(u, v);
    }

    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_ael.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"

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

#line 2 "graph/ael.hpp"

//! Adjacency edge list
//  Doesn't support g[v][i] D:

template<class E> struct AEL {
    using internal_edge = pair<E, int>;

    AEL() {}
    AEL(int _n) : n(_n), head(n, -1) {}
    AEL(int _n, int m) : AEL(_n) { edges.reserve(m); }

    int size() const { return n; }

    void add_edge(int u, const E &e) {
        edges.emplace_back(e, head[u]), head[u] = (int)edges.size() - 1;
    }

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

    struct iterator {
        AEL *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 AEL *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> head;
    vector<internal_edge> 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_ael.test.cpp"

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

    AEL<int> g(n);
    for (int u, v; m--;) {
        cin >> u >> v;
        g.add_edge(u, v);
    }

    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	4 ms	4 MB
g++	large_cycle_00	AC	104 ms	62 MB
g++	max_random_00	AC	147 ms	30 MB
g++	max_random_01	AC	145 ms	30 MB
g++	max_random_02	AC	147 ms	29 MB
g++	max_random_03	AC	154 ms	30 MB
g++	max_random_04	AC	150 ms	29 MB
g++	random_00	AC	123 ms	27 MB
g++	random_01	AC	137 ms	29 MB
g++	random_02	AC	53 ms	13 MB
g++	random_03	AC	65 ms	25 MB
g++	random_04	AC	56 ms	24 MB
clang++	example_00	AC	4 ms	4 MB
clang++	large_cycle_00	AC	99 ms	51 MB
clang++	max_random_00	AC	144 ms	29 MB
clang++	max_random_01	AC	155 ms	30 MB
clang++	max_random_02	AC	152 ms	29 MB
clang++	max_random_03	AC	170 ms	29 MB
clang++	max_random_04	AC	162 ms	29 MB
clang++	random_00	AC	122 ms	27 MB
clang++	random_01	AC	135 ms	28 MB
clang++	random_02	AC	53 ms	12 MB
clang++	random_03	AC	61 ms	25 MB
clang++	random_04	AC	59 ms	24 MB