#include "tree/block-cut-tree.hpp"
#pragma once #include "../graph/biconnected-components.hpp" // aux : block cut tree // id(V) : new id of node V // is_arti(V) : return if V is articulation template <typename G> struct BlockCutTree { const G& g; BiConnectedComponents<G> bcc; vector<vector<int>> aux; vector<int> idar, idcc; BlockCutTree(const G& _g) : g(_g), bcc(g) { build(); } void build() { auto ar = bcc.articulation; idar.resize(g.size(), -1); idcc.resize(g.size(), -1); for (int i = 0; i < (int)ar.size(); i++) idar[ar[i]] = i; aux.resize(ar.size() + bcc.bc.size()); vector<int> last(g.size(), -1); for (int i = 0; i < (int)bcc.bc.size(); i++) { vector<int> st; for (auto& [u, v] : bcc.bc[i]) st.push_back(u), st.push_back(v); for (auto& u : st) { if (idar[u] == -1) idcc[u] = i + ar.size(); else if(last[u] != i){ add(i + ar.size(), idar[u]); last[u] = i; } } } } vector<int>& operator[](int i) { return aux[i]; } int size() const { return aux.size(); } int id(int i) { return idar[i] == -1 ? idcc[i] : idar[i]; } bool is_arti(int i) { return idar[i] != -1; } int arti() const { return bcc.articulation.size(); } private: void add(int i, int j) { if (i == -1 or j == -1) return; aux[i].push_back(j); aux[j].push_back(i); }; }; /** * @brief Block Cut Tree */
#line 2 "tree/block-cut-tree.hpp" #line 2 "graph/biconnected-components.hpp" #line 2 "graph/lowlink.hpp" #include <vector> using namespace std; #line 2 "graph/graph-template.hpp" template <typename T> struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnweightedGraph = vector<vector<int>>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template <typename T> WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph<T> g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].emplace_back(x, y, c); if (!is_directed) g[y].emplace_back(y, x, c); } return g; } // Input of Edges template <typename T> Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges<T> es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template <typename T> vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector<vector<T>> d(N, vector<T>(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } /** * @brief グラフテンプレート * @docs docs/graph/graph-template.md */ #line 7 "graph/lowlink.hpp" // bridge ... 橋 (辺 (u, v) が u < v となるように格納) // articulation point ... 関節点 template <typename G> struct LowLink { const G &g; int N; vector<int> ord, low, articulation; vector<pair<int, int> > bridge; LowLink(const G &_g) : g(_g), N(g.size()), ord(N, -1), low(N, -1) { for (int i = 0, k = 0; i < N; i++) { if (ord[i] == -1) { k = dfs(i, k, -1); } } } int dfs(int idx, int k, int par) { low[idx] = (ord[idx] = k++); int cnt = 0; bool arti = false, second = false; for (auto &to : g[idx]) { if (ord[to] == -1) { cnt++; k = dfs(to, k, idx); low[idx] = min(low[idx], low[to]); arti |= (par != -1) && (low[to] >= ord[idx]); if (ord[idx] < low[to]) { bridge.emplace_back(minmax(idx, (int)to)); } } else if (to != par || second) { low[idx] = min(low[idx], ord[to]); } else { second = true; } } arti |= par == -1 && cnt > 1; if (arti) articulation.push_back(idx); return k; } }; #line 4 "graph/biconnected-components.hpp" template <typename G> struct BiConnectedComponents : LowLink<G> { using LL = LowLink<G>; vector<int> used; vector<vector<pair<int, int> > > bc; vector<pair<int, int> > tmp; BiConnectedComponents(const G &_g) : LL(_g) { build(); } void build() { used.assign(this->g.size(), 0); for (int i = 0; i < (int)used.size(); i++) { if (!used[i]) dfs(i, -1); } } void dfs(int idx, int par) { used[idx] = true; for (auto &to : this->g[idx]) { if (to == par) continue; if (!used[to] || this->ord[to] < this->ord[idx]) { tmp.emplace_back(minmax<int>(idx, to)); } if (!used[to]) { dfs(to, idx); if (this->low[to] >= this->ord[idx]) { bc.emplace_back(); while(true) { auto e = tmp.back(); bc.back().emplace_back(e); tmp.pop_back(); if (e.first == min<int>(idx, to) && e.second == max<int>(idx, to)) { break; } } } } } } }; /** * @brief 二重頂点連結分解 */ #line 4 "tree/block-cut-tree.hpp" // aux : block cut tree // id(V) : new id of node V // is_arti(V) : return if V is articulation template <typename G> struct BlockCutTree { const G& g; BiConnectedComponents<G> bcc; vector<vector<int>> aux; vector<int> idar, idcc; BlockCutTree(const G& _g) : g(_g), bcc(g) { build(); } void build() { auto ar = bcc.articulation; idar.resize(g.size(), -1); idcc.resize(g.size(), -1); for (int i = 0; i < (int)ar.size(); i++) idar[ar[i]] = i; aux.resize(ar.size() + bcc.bc.size()); vector<int> last(g.size(), -1); for (int i = 0; i < (int)bcc.bc.size(); i++) { vector<int> st; for (auto& [u, v] : bcc.bc[i]) st.push_back(u), st.push_back(v); for (auto& u : st) { if (idar[u] == -1) idcc[u] = i + ar.size(); else if(last[u] != i){ add(i + ar.size(), idar[u]); last[u] = i; } } } } vector<int>& operator[](int i) { return aux[i]; } int size() const { return aux.size(); } int id(int i) { return idar[i] == -1 ? idcc[i] : idar[i]; } bool is_arti(int i) { return idar[i] != -1; } int arti() const { return bcc.articulation.size(); } private: void add(int i, int j) { if (i == -1 or j == -1) return; aux[i].push_back(j); aux[j].push_back(i); }; }; /** * @brief Block Cut Tree */