グラフ/強連結成分分解
(test/graph/strongly_connected_components.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.yosupo.jp/problem/scc

Depends on

• 辺 (include/emthrm/graph/edge.hpp)
• 強連結成分 (strongly connected components) 分解 (include/emthrm/graph/strongly_connected_components.hpp)

Code

/*
 * @title グラフ/強連結成分分解
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc
 */

#include <iostream>
#include <vector>

#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/strongly_connected_components.hpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
  while (m--) {
    int a, b;
    std::cin >> a >> b;
    graph[a].emplace_back(a, b);
  }
  const std::vector<std::vector<int>> ans =
      emthrm::StronglyConnectedComponents<bool, true>(graph).vertices;
  const int k = ans.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    const int l = ans[i].size();
    std::cout << l << ' ';
    for (int j = 0; j < l; ++j) {
      std::cout << ans[i][j] << " \n"[j + 1 == l];
    }
  }
  return 0;
}

#line 1 "test/graph/strongly_connected_components.test.cpp"
/*
 * @title グラフ/強連結成分分解
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/strongly_connected_components.hpp"



// #include <algorithm>
#include <ranges>
#line 7 "include/emthrm/graph/strongly_connected_components.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 9 "include/emthrm/graph/strongly_connected_components.hpp"

namespace emthrm {

template <typename CostType, bool IS_FULL_VER = false>
struct StronglyConnectedComponents {
  std::vector<int> id;
  std::vector<std::vector<int>> vertices;
  std::vector<std::vector<Edge<CostType>>> g;

  explicit StronglyConnectedComponents(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : n(graph.size()), is_used(n, false), graph(graph), rgraph(n) {
    for (int i = 0; i < n; ++i) {
      if (!is_used[i]) dfs(i);
    }
    id.assign(n, -1);
    order.reserve(n);
    for (int i = 0; i < n; ++i) {
      for (const Edge<CostType>& e : graph[i]) {
        rgraph[e.dst].emplace_back(e.dst, e.src, e.cost);
      }
    }
    int m = 0;
    for (int i = n - 1; i >= 0; --i) {
      if (id[order[i]] == -1) {
        if constexpr (IS_FULL_VER) vertices.emplace_back();
        rdfs(order[i], m++);
      }
    }
    g.resize(m);
    for (int i = 0; i < n; ++i) {
      for (const Edge<CostType>& e : graph[i]) {
        if (id[i] != id[e.dst]) g[id[i]].emplace_back(id[i], id[e.dst], e.cost);
      }
    }
    // if constexpr (IS_FULL_VER) {
    //   for (int i = 0; i < m; ++i) {
    //     std::sort(vertices[i].begin(), vertices[i].end());
    //   }
    // }
  }

 private:
  const int n;
  std::vector<bool> is_used;
  std::vector<int> order;
  const std::vector<std::vector<Edge<CostType>>> graph;
  std::vector<std::vector<Edge<CostType>>> rgraph;

  void dfs(const int ver) {
    is_used[ver] = true;
    for (const int e : graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (!is_used[e]) dfs(e);
    }
    order.emplace_back(ver);
  }

  void rdfs(const int ver, const int m) {
    id[ver] = m;
    if constexpr (IS_FULL_VER) vertices.back().emplace_back(ver);
    for (const int e : rgraph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (id[e] == -1) rdfs(e, m);
    }
  }
};

}  // namespace emthrm


#line 12 "test/graph/strongly_connected_components.test.cpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<bool>>> graph(n);
  while (m--) {
    int a, b;
    std::cin >> a >> b;
    graph[a].emplace_back(a, b);
  }
  const std::vector<std::vector<int>> ans =
      emthrm::StronglyConnectedComponents<bool, true>(graph).vertices;
  const int k = ans.size();
  std::cout << k << '\n';
  for (int i = 0; i < k; ++i) {
    const int l = ans[i].size();
    std::cout << l << ' ';
    for (int j = 0; j < l; ++j) {
      std::cout << ans[i][j] << " \n"[j + 1 == l];
    }
  }
  return 0;
}

Back to top page