library/graph/SCC.hpp

• View this file on GitHub
• Last update: 2025-11-24 18:49:07+09:00
• Include: #include "library/graph/SCC.hpp"

Depends on

• build/pch/stdc++.hpp
• library/graph/Graph.hpp
• library/graph/ReverseGraph.hpp

Verified with

• test/library-checker/Graph/SCC.test.cpp

Code

#pragma once
#include "library/graph/Graph.hpp"
#include "library/graph/ReverseGraph.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
template <typename DirectedGraph> class SCC {
    int n;
    DirectedGraph G, R;
    std::vector<int> visit, belong;
    std::vector<uint8_t> used;
    void dfs(int v) {
        used[v] = true;
        for (int to : G[v])
            if (!used[to])
                dfs(to);
        visit.push_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = true;
        belong[v] = k;
        for (int to : R[v])
            if (!used[to])
                rdfs(to, k);
    }

  public:
    Graph DAG;
    std::vector<std::vector<int>> component;
    SCC(const DirectedGraph &G) : n(G.n), G(G), belong(n), used(n, false) {
        assert(G.is_prepared());
        visit.reserve(n);
        R = reverse_graph(G);
        REP_(v, n) if (!used[v]) dfs(v);
        std::ranges::fill(used, false);
        std::ranges::reverse(visit);
        int k = 0;
        for (const int &v : visit)
            if (!used[v])
                rdfs(v, k++);
        std::vector<std::vector<int>> edges(k);
        component.resize(k);
        REP_(v, n) {
            component[belong[v]].push_back(v);
            for (int to : G[v])
                if (belong[v] != belong[to])
                    edges[belong[v]].push_back(belong[to]);
        }
        DAG = Graph(k);
        REP_(from, k) {
            std::ranges::sort(edges[from]);
            REP_(i, edges[from].size())
            if (!i || edges[from][i] != edges[from][i - 1])
                DAG.add_arc(from, edges[from][i]);
        }
    }
    int operator[](int k) { return belong[k]; }
};
#undef REP_

#line 2 "library/graph/Graph.hpp"

#include <cassert>
#include <iostream>
#include <vector>

struct Edge {
    int from, to;
    Edge() = default;
    Edge(int from, int to) : from(from), to(to) {}
    operator int() const { return to; }
};

struct Graph {
    int n;
    using edge_type = Edge;
    std::vector<edge_type> edges;

  protected:
    std::vector<int> in_deg;
    bool prepared;
    class OutgoingEdges {
        Graph *g;
        int l, r;

      public:
        OutgoingEdges(Graph *g, int l, int r) : g(g), l(l), r(r) {}
        edge_type *begin() { return &(g->edges[l]); }
        edge_type *end() { return &(g->edges[r]); }
        edge_type &operator[](int i) { return g->edges[l + i]; }
        int size() const { return r - l; }
    };
    class ConstOutgoingEdges {
        const Graph *g;
        int l, r;

      public:
        ConstOutgoingEdges(const Graph *g, int l, int r) : g(g), l(l), r(r) {}
        const edge_type *begin() const { return &(g->edges[l]); }
        const edge_type *end() const { return &(g->edges[r]); }
        const edge_type &operator[](int i) const { return g->edges[l + i]; }
        int size() const { return r - l; }
    };

  public:
    OutgoingEdges operator[](int v) {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }
    const ConstOutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }

    bool is_prepared() const { return prepared; }

    Graph() : n(0), in_deg(1, 0), prepared(false) {}
    Graph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
    Graph(int n, int m, bool directed = false, int indexed = 1)
        : n(n), in_deg(n + 1, 0), prepared(false) {
        scan(m, directed, indexed);
    }

    void resize(int n) { n = n; }

    void add_arc(int from, int to) {
        assert(!prepared);
        assert(0 <= from and from < n and 0 <= to and to < n);
        edges.emplace_back(from, to);
        in_deg[from + 1]++;
    }
    void add_edge(int u, int v) {
        add_arc(u, v);
        add_arc(v, u);
    }
    void add_arc(const edge_type &e) { add_arc(e.from, e.to); }
    void add_edge(const edge_type &e) { add_edge(e.from, e.to); }

    void scan(int m, bool directed = false, int indexed = 1) {
        edges.reserve(directed ? m : 2 * m);
        while (m--) {
            int u, v;
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            if (directed)
                add_arc(u, v);
            else
                add_edge(u, v);
        }
        build();
    }

    void build() {
        assert(!prepared);
        prepared = true;
        for (int v = 0; v < n; v++)
            in_deg[v + 1] += in_deg[v];
        std::vector<edge_type> new_edges(in_deg.back());
        auto counter = in_deg;
        for (auto &&e : edges)
            new_edges[counter[e.from]++] = e;
        edges = new_edges;
    }

    void graph_debug() const {
#ifndef __LOCAL
        return;
#endif
        assert(prepared);
        for (int from = 0; from < n; from++) {
            std::cerr << from << ";";
            for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
                std::cerr << edges[i].to << " ";
            std::cerr << "\n";
        }
    }
};
#line 2 "library/graph/ReverseGraph.hpp"
template <typename GRAPH> GRAPH reverse_graph(const GRAPH &g) {
    GRAPH r(g.n);
    for (auto e : g.edges) {
        std::swap(e.from, e.to);
        r.add_arc(e);
    }
    r.build();
    return r;
}
#line 4 "library/graph/SCC.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
template <typename DirectedGraph> class SCC {
    int n;
    DirectedGraph G, R;
    std::vector<int> visit, belong;
    std::vector<uint8_t> used;
    void dfs(int v) {
        used[v] = true;
        for (int to : G[v])
            if (!used[to])
                dfs(to);
        visit.push_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = true;
        belong[v] = k;
        for (int to : R[v])
            if (!used[to])
                rdfs(to, k);
    }

  public:
    Graph DAG;
    std::vector<std::vector<int>> component;
    SCC(const DirectedGraph &G) : n(G.n), G(G), belong(n), used(n, false) {
        assert(G.is_prepared());
        visit.reserve(n);
        R = reverse_graph(G);
        REP_(v, n) if (!used[v]) dfs(v);
        std::ranges::fill(used, false);
        std::ranges::reverse(visit);
        int k = 0;
        for (const int &v : visit)
            if (!used[v])
                rdfs(v, k++);
        std::vector<std::vector<int>> edges(k);
        component.resize(k);
        REP_(v, n) {
            component[belong[v]].push_back(v);
            for (int to : G[v])
                if (belong[v] != belong[to])
                    edges[belong[v]].push_back(belong[to]);
        }
        DAG = Graph(k);
        REP_(from, k) {
            std::ranges::sort(edges[from]);
            REP_(i, edges[from].size())
            if (!i || edges[from][i] != edges[from][i - 1])
                DAG.add_arc(from, edges[from][i]);
        }
    }
    int operator[](int k) { return belong[k]; }
};
#undef REP_

Back to top page