This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#include "graph/low_link.hpp"
Graph<T> g; LowLink lk(g); auto articulations = lk.articulations // 関節点の集合 auto bridges = lk.bridges // 橋である辺の集合
#pragma once #include "graph/graph_template.hpp" template <class T> struct LowLink { int n; std::vector<int> ord, low; std::vector<std::vector<int>> dfs_tree; std::vector<int> articulations; std::vector<std::pair<int, int>> bridges; // edges {u, v} (u < v) std::vector<int> roots; LowLink(Graph<T>& g) : n((int)(g.size())), ord(n, -1), low(n, -1), dfs_tree(n) { int ord_id = 0; auto dfs = [&](auto f, int cur, int par) -> void { low[cur] = ord[cur] = ord_id++; bool is_articulation = false; for (auto&& e : g[cur]) { if (ord[e.to] == -1) { // DFS 木上の辺に対する処理 f(f, e.to, cur); dfs_tree[cur].push_back(e.to); // e が DFS 木に含まれているので後退辺をすでに通った low[e.to] を使って更新して良い low[cur] = std::min(low[cur], low[e.to]); is_articulation |= (par != -1) and (ord[cur] <= low[e.to]); if (ord[cur] < low[e.to]) { bridges.emplace_back(std::minmax(cur, e.to)); } } else if (e.to != par) { // 後退辺に対する処理 // Todo: multiple edges low[cur] = std::min(low[cur], ord[e.to]); } } is_articulation |= par == -1 and (int)(dfs_tree[cur].size()) > 1; if (is_articulation) articulations.push_back(cur); return; }; for (int i = 0; i < n; i++) { if (ord[i] == -1) { roots.push_back(i); dfs(dfs, i, -1); } } } // 連結成分数 int count_components() { return (int)(roots.size()); } // 頂点 x を取り除くともともと 1 つだった連結成分がいくつになるか int count_components_remove(int x) { if (std::binary_search(roots.begin(), roots.end(), x)) { return (int)(dfs_tree[x].size()); } else { int c = 0; for (auto&& e : dfs_tree[x]) { if (ord[x] <= low[e]) c++; } // 親の分で +1 return c + 1; } } };
#line 2 "graph/low_link.hpp" #line 2 "graph/graph_template.hpp" #include <vector> #include <cassert> template <class T> struct Edge { int from, to; T cost; int id; Edge() = default; Edge(const int from, const int to, const T cost = T(1), const int id = -1) : from(from), to(to), cost(cost), id(id) {} friend bool operator<(const Edge<T>& a, const Edge<T>& b) { return a.cost < b.cost; } friend std::ostream& operator<<(std::ostream& os, const Edge<T>& e) { // output format: {id: cost(from, to) = cost} return os << "{" << e.id << ": cost(" << e.from << ", " << e.to << ") = " << e.cost << "}"; } }; template <class T> using Edges = std::vector<Edge<T>>; template <class T> struct Graph { struct EdgeIterators { public: using Iterator = typename std::vector<Edge<T>>::iterator; EdgeIterators() = default; EdgeIterators(const Iterator& begit, const Iterator& endit) : begit(begit), endit(endit) {} Iterator begin() const { return begit; } Iterator end() const { return endit; } size_t size() const { return std::distance(begit, endit); } Edge<T>& operator[](int i) const { return begit[i]; } private: Iterator begit, endit; }; int n, m; bool is_build, is_directed; std::vector<Edge<T>> edges; // CSR (Compressed Row Storage) 形式用 std::vector<int> start; std::vector<Edge<T>> csr_edges; Graph() = default; Graph(const int n, const bool directed = false) : n(n), m(0), is_build(false), is_directed(directed), start(n + 1, 0) {} // 辺を追加し, その辺が何番目に追加されたかを返す int add_edge(const int from, const int to, const T cost = T(1), int id = -1) { assert(!is_build); assert(0 <= from and from < n); assert(0 <= to and to < n); if (id == -1) id = m; edges.emplace_back(from, to, cost, id); return m++; } // CSR 形式でグラフを構築 void build() { assert(!is_build); for (auto&& e : edges) { start[e.from + 1]++; if (!is_directed) start[e.to + 1]++; } for (int v = 0; v < n; v++) start[v + 1] += start[v]; auto counter = start; csr_edges.resize(start.back() + 1); for (auto&& e : edges) { csr_edges[counter[e.from]++] = e; if (!is_directed) csr_edges[counter[e.to]++] = Edge(e.to, e.from, e.cost, e.id); } is_build = true; } EdgeIterators operator[](int i) { if (!is_build) build(); return EdgeIterators(csr_edges.begin() + start[i], csr_edges.begin() + start[i + 1]); } size_t size() const { return (size_t)(n); } friend std::ostream& operator<<(std::ostream& os, Graph<T>& g) { os << "["; for (int i = 0; i < (int)(g.size()); i++) { os << "["; for (int j = 0; j < (int)(g[i].size()); j++) { os << g[i][j]; if (j + 1 != (int)(g[i].size())) os << ", "; } os << "]"; if (i + 1 != (int)(g.size())) os << ", "; } return os << "]"; } }; #line 4 "graph/low_link.hpp" template <class T> struct LowLink { int n; std::vector<int> ord, low; std::vector<std::vector<int>> dfs_tree; std::vector<int> articulations; std::vector<std::pair<int, int>> bridges; // edges {u, v} (u < v) std::vector<int> roots; LowLink(Graph<T>& g) : n((int)(g.size())), ord(n, -1), low(n, -1), dfs_tree(n) { int ord_id = 0; auto dfs = [&](auto f, int cur, int par) -> void { low[cur] = ord[cur] = ord_id++; bool is_articulation = false; for (auto&& e : g[cur]) { if (ord[e.to] == -1) { // DFS 木上の辺に対する処理 f(f, e.to, cur); dfs_tree[cur].push_back(e.to); // e が DFS 木に含まれているので後退辺をすでに通った low[e.to] を使って更新して良い low[cur] = std::min(low[cur], low[e.to]); is_articulation |= (par != -1) and (ord[cur] <= low[e.to]); if (ord[cur] < low[e.to]) { bridges.emplace_back(std::minmax(cur, e.to)); } } else if (e.to != par) { // 後退辺に対する処理 // Todo: multiple edges low[cur] = std::min(low[cur], ord[e.to]); } } is_articulation |= par == -1 and (int)(dfs_tree[cur].size()) > 1; if (is_articulation) articulations.push_back(cur); return; }; for (int i = 0; i < n; i++) { if (ord[i] == -1) { roots.push_back(i); dfs(dfs, i, -1); } } } // 連結成分数 int count_components() { return (int)(roots.size()); } // 頂点 x を取り除くともともと 1 つだった連結成分がいくつになるか int count_components_remove(int x) { if (std::binary_search(roots.begin(), roots.end(), x)) { return (int)(dfs_tree[x].size()); } else { int c = 0; for (auto&& e : dfs_tree[x]) { if (ord[x] <= low[e]) c++; } // 親の分で +1 return c + 1; } } };