Strongly Connected Components
(lib/graph/scc.hpp)

• View this file on GitHub
• Last update: 2024-06-14 09:23:51+08:00
• Include: #include "lib/graph/scc.hpp"

Depends on

• Internal Definition (lib/internal.hpp)

Verified with

• verify/graph/scc.test.cpp

Code

#pragma once
#include "lib/internal.hpp"

/**
 * @brief Strongly Connected Components
 * 
 */
struct scc_graph
{
  int n;
  std::vector<std::vector<int>> adj;

  scc_graph(int n) : n(n), adj(n) {}

  void add_edge(int u, int v) { adj[u].emplace_back(v); }

  std::pair<int, std::vector<int>> solve()
  {
    std::vector<int> dfn(n, -1), low(n, -1), stk;
    std::vector<bool> vis(n);
    std::vector<int> belong(n, -1);
    int scc_cnt = 0;
    int cnt = 0;
    auto dfs = [&](auto &&self, int u) -> void {
      dfn[u] = low[u] = cnt++;
      stk.emplace_back(u);
      vis[u] = true;
      for (auto v : adj[u]) {
        if (dfn[v] == -1) {
          self(self, v);
          low[u] = std::min(low[u], low[v]);
        } else if (vis[v]) {
          low[u] = std::min(low[u], dfn[v]);
        }
      }
      if (low[u] == dfn[u]) {
        while (true) {
          int x = stk.back();
          stk.pop_back();
          vis[x] = false;
          belong[x] = scc_cnt;
          if (x == u) break;
        }
        scc_cnt++;
      }
    };
    for (int i = 0; i < n; i++) {
      if (belong[i] == -1) dfs(dfs, i);
    }
    return {scc_cnt, belong};
  }
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: lib/internal.hpp: line 4: #pragma once found in a non-first line

Back to top page