cpp/graph/lowlink.hpp

• View this file on GitHub
• Last update: 2024-11-03 09:29:45+09:00
• Include: #include "cpp/graph/lowlink.hpp"
• Link: https://algo-logic.info/articulation-points/

Depends on

• cpp/graph/edge.hpp
• グラフ (隣接リスト形式) (cpp/graph/graph_list.hpp)
• 共通ヘッダー (cpp/template/small_template.hpp)

Verified with

• cpp/verify/articulation_points.test.cpp
• cpp/verify/bridges.test.cpp

Code

#pragma once
#include "graph/graph_list.hpp"
#include "template/small_template.hpp"

/**
 * Lowlink 関節点・橋の列挙
 * 関節点 削除すると連結成分数が増加する頂点
 * 橋 削除すると連結成分数が増加する辺
 * 返り値：関節点, 橋(from, to)
 * O(V + E log E) (Lowlink + sort)
 * https://algo-logic.info/articulation-points/
 */
template <class Cost, class E>
pair<vector<int>, vector<pair<int, int>>> ListGraph<Cost, E>::lowlink() {
  using P = pair<int, int>;
  vector<bool> visited(n_, false);
  // ord: 頂点を探索した順番 low: DFS木にない辺を高々1回通って踏める最小のord
  vector<int> ord(n_, 0), low(n_, 0), articulation_points;
  vector<P> bridges;
  int visit_count = 0;

  auto dfs = [&](auto self, int v, int parent) -> void {
    visited[v] = true;
    low[v] = ord[v] = visit_count++;
    bool is_articular = false;
    int child_count = 0;
    for (auto &e : adj[v]) {
      if (!visited[e.to]) {
        child_count++;
        self(self, e.to, v);
        low[v] = min(low[v], low[e.to]);
        if (parent != -1 && ord[v] <= low[e.to]) {
          is_articular = true;
        }
        if (ord[v] < low[e.to]) {
          bridges.emplace_back(min(v, e.to), max(v, e.to));
        }
      } else if (e.to != parent) {
        low[v] = min(low[v], ord[e.to]);
      }
    }
    if (parent == -1 && child_count >= 2) {
      is_articular = true;
    }
    if (is_articular) {
      articulation_points.emplace_back(v);
    }
  };
  for (int i = 0; i < n_; ++i) {
    if (!visited[i]) {
      dfs(dfs, i, -1);
    }
  }
  sort(articulation_points.begin(), articulation_points.end());
  sort(bridges.begin(), bridges.end());
  return {articulation_points, bridges};
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/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 "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph_list.hpp: line -1: no such header

Back to top page