Graph/Digraph/Strongly_Connected_Components.hpp

• View this file on GitHub
• Last update: 2025-08-17 23:17:56+09:00
• Include: #include "Graph/Digraph/Strongly_Connected_Components.hpp"

Depends on

• Graph/Digraph/Digraph.hpp

Verified with

• verify/yosupo_library_checker/graph/Strongly_Connected_Components.test.cpp

Code

#include"Digraph.hpp"

namespace Digraph {
    class Strongly_Connected_Components {
        public:
        vector<vector<int>> components;
        vector<int> group;

        private:
        vector<int> order;
        vector<bool> used;

        public:
        Strongly_Connected_Components(const Digraph &D) {
            int n = D.order();

            used.assign(n, false);

            for (int i = 0; i < n; i++) {
                unless(used[i]) { dfs1(D, i); }
            }

            reverse(all(order));
            group.assign(n, -1);

            for (int v: order) {
                unless(group[v] == -1) { continue; }

                components.emplace_back(vector<int>());
                dfs2(D, v);
            }
        }

        private:
        void dfs1(const Digraph &D, int v) {
            used[v] = true;
            for (auto arc_id: D.successors(v)) {
                auto arc = D.get_arc(arc_id);
                int w = arc.target;

                unless(used[w]) { dfs1(D, w); }
            }

            order.emplace_back(v);
        }

        void dfs2(const Digraph &D, int v) {
            components[group[v] = components.size() - 1].emplace_back(v);

            for (auto arc_id: D.predecessors(v)) {
                auto arc = D.get_arc(arc_id);
                int w = arc.source;
                if (group[w] == -1) { dfs2(D, w); }
            }
        }
    };
}

#line 2 "Graph/Digraph/Digraph.hpp"

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

namespace Digraph {
  struct Arc {
    int id, source, target;

    Arc(int id, int source, int target): id(id), source(source), target(target) {}
  };

  class Digraph {
    private:
    int arc_id_offset;
    vector<vector<int>> adjacent_out, adjacent_in;
    vector<Arc> arcs;

    public:
    Digraph(int n, int arc_id_offset = 0): arc_id_offset(arc_id_offset) {
        adjacent_out.assign(n, {});
        adjacent_in.assign(n, {});
        arcs.resize(arc_id_offset, Arc(-1, -1, -1));
      }
    
    inline int order() const { return int(adjacent_in.size()); }

    inline int size() const { return int(arcs.size()) - arc_id_offset; }

    // 頂点 u から頂点 v への重み w の弧を追加する.
    int add_arc(int u, int v){
      int id = int(arcs.size());

      adjacent_out[u].emplace_back(id);
      adjacent_in[v].emplace_back(id);
      arcs.emplace_back(id, u, v);

      return id;
    }

    // 頂点 u から出る弧の ID のリストを取得
    inline const std::vector<int>& successors(int u) const { return adjacent_out[u]; }

    // 頂点 u に入る弧の ID のリストを取得
    inline const std::vector<int>& predecessors(int u) const { return adjacent_in[u]; }

    // 弧 ID が id である弧を取得する.
    inline const Arc& get_arc(int id) const { return arcs[id]; }
    inline Arc& get_arc(int id) { return arcs[id]; }
  };
}
#line 2 "Graph/Digraph/Strongly_Connected_Components.hpp"

namespace Digraph {
    class Strongly_Connected_Components {
        public:
        vector<vector<int>> components;
        vector<int> group;

        private:
        vector<int> order;
        vector<bool> used;

        public:
        Strongly_Connected_Components(const Digraph &D) {
            int n = D.order();

            used.assign(n, false);

            for (int i = 0; i < n; i++) {
                unless(used[i]) { dfs1(D, i); }
            }

            reverse(all(order));
            group.assign(n, -1);

            for (int v: order) {
                unless(group[v] == -1) { continue; }

                components.emplace_back(vector<int>());
                dfs2(D, v);
            }
        }

        private:
        void dfs1(const Digraph &D, int v) {
            used[v] = true;
            for (auto arc_id: D.successors(v)) {
                auto arc = D.get_arc(arc_id);
                int w = arc.target;

                unless(used[w]) { dfs1(D, w); }
            }

            order.emplace_back(v);
        }

        void dfs2(const Digraph &D, int v) {
            components[group[v] = components.size() - 1].emplace_back(v);

            for (auto arc_id: D.predecessors(v)) {
                auto arc = D.get_arc(arc_id);
                int w = arc.source;
                if (group[w] == -1) { dfs2(D, w); }
            }
        }
    };
}

Back to top page