test/library-checker/scc.test.cpp

View this file on GitHub
Last update: 2023-06-27 00:42:25+09:00
Problem: https://judge.yosupo.jp/problem/scc

Depends on

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc

#include "src/cpp-template/header/size-alias.hpp"
#include "src/graph/decomposition/strongly-connected-components.hpp"

#include <iostream>
#include <vector>

namespace luz {

  void main_() {
    usize n, m;
    std::cin >> n >> m;

    SCCGraph g(n);
    while (m--) {
      usize u, v;
      std::cin >> u >> v;
      g.add_directed_edge(u, v);
    }

    auto groups = g.get_scc_list();
    std::cout << groups.size() << std::endl;

    for (auto& group: groups) {
      std::cout << group.size();
      for (auto &v: group) {
        std::cout << " " << v;
      }
      std::cout << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "test/library-checker/scc.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

}
#line 2 "src/graph/decomposition/strongly-connected-components.hpp"

#include <vector>
#line 5 "src/graph/decomposition/strongly-connected-components.hpp"

namespace luz {

  struct SCCGraph {
    using usize = std::size_t;
    using graph = std::vector< std::vector< usize > >;

    usize n;
    graph g;
    std::vector< usize > S, B, I;

    void dfs(usize v, graph &scc) {
      B.emplace_back(I[v] = S.size());
      S.emplace_back(v);

      for (auto u: g[v]) {
        if (I[u]) {
          while (I[u] < B.back()) B.pop_back();
        } else {
          dfs(u, scc);
        }
      }
      if (I[v] != B.back()) return;

      scc.emplace_back();
      B.pop_back();
      while (I[v] < S.size()) {
        scc.back().emplace_back(S.back());
        I[S.back()] = n + scc.size();
        S.pop_back();
      }
    }

   public:
    SCCGraph(usize n) : n(n), g(n) {}

    void add_directed_edge(usize from, usize to) {
      g[from].emplace_back(to);
    }

    graph get_scc_list() {
      graph scc;
      I.assign(n, 0);
      S = B = {};
      for (usize v = 0; v < n; v++) {
        if (not I[v]) dfs(v, scc);
      }
      return {scc.rbegin(), scc.rend()};
    }

  };

} // namespace luz
#line 5 "test/library-checker/scc.test.cpp"

#include <iostream>
#line 8 "test/library-checker/scc.test.cpp"

namespace luz {

  void main_() {
    usize n, m;
    std::cin >> n >> m;

    SCCGraph g(n);
    while (m--) {
      usize u, v;
      std::cin >> u >> v;
      g.add_directed_edge(u, v);
    }

    auto groups = g.get_scc_list();
    std::cout << groups.size() << std::endl;

    for (auto& group: groups) {
      std::cout << group.size();
      for (auto &v: group) {
        std::cout << " " << v;
      }
      std::cout << std::endl;
    }
  }

} // namespace luz

int main() {
  luz::main_();
}