Block Cut Tree
(tree/block-cut-tree.hpp)

• View this file on GitHub
• Last update: 2024-05-03 23:21:26+09:00
• Include: #include "tree/block-cut-tree.hpp"

Depends on

• 二重頂点連結分解 (graph/biconnected-components.hpp)
• グラフテンプレート (graph/graph-template.hpp)
• graph/lowlink.hpp

Verified with

• verify/verify-aoj-other/aoj-3022.test.cpp
• verify/verify-yuki/yuki-1326.test.cpp

Code

#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([[maybe_unused]] 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
 */

Back to top page