Online-Dynamic-Connectivity (src/DataStructure/OnlineDynamicConnectivity.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-12 14:04:05+09:00
• Include: #include "src/DataStructure/OnlineDynamicConnectivity.hpp"
• Link: View error logs on GitHub Actions

概要

オンラインでグラフの辺の追加・削除を行いながら、連結性や連結成分ごとの集約値をクエリできるデータ構造。 内部で Euler Tour Tree を利用している。

テンプレートパラメータ

• typename M: 頂点の値に乗せるモノイド。
  • M::T: 値の型
  • M::ti(): 単位元
  • M::op(l, r): 演算
• std::size_t NODE_SIZE: Euler Tour Tree が内部で確保するノードの最大サイズ。デフォルトは 4'000'000。

使い方

OnlineDynamicConnectivity<M> dicon(N) のように宣言する。

関数	説明	計算量
dicon.link(u, v)	頂点 u と v の間に辺を追加する。	$O((\log N)^2)$
dicon.cut(u, v)	頂点 u と v の間の辺を削除する。	$O((\log N)^2)$
dicon.connected(u, v)	頂点 u と v が連結か判定する。	$O(\log N)$
dicon.set(k, val)	頂点 k の値を val に設定する。	$O(\log N)$
dicon.get(k) / dicon[k]	頂点 k の値を取得する。	$O(\log N)$
dicon.prod(k)	頂点 k が属する連結成分の集約値を取得する。	$O(\log N)$
dicon.apply(k, f)	頂点 k が属する連結成分の各頂点に作用 f を適用する。	$O(\log N)$
dicon.size(k)	頂点 k が属する連結成分のサイズを取得する。	$O(\log N)$

コード例

// 連結成分ごとの合計値を管理する例
struct Monoid {
    using T = long long;
    static T ti() { return 0; }
    static T op(T a, T b) { return a + b; }
};

OnlineDynamicConnectivity<Monoid> dicon(N);

// 頂点 0 に値 10 をセット
dicon.set(0, 10);

// 辺 (0, 1) を追加
dicon.link(0, 1);

// 頂点 0 が属する連結成分の合計値を取得
long long sum = dicon.prod(0);

計算量

• link, cut: $O((\log N)^2)$
• connected, set, get, prod, apply, size: $O(\log N)$

参考

https://qiita.com/hotman78/items/78cd3aa50b05a57738d4

Verify

• Educational Codeforces Round 62 F. Extending Set of Points
• AOJ 2235 - Chain Disconnection
• AOJ 2893 - To Star a New Journey
• Yosupo Judge - Dynamic Graph Vertex Add Component Sum

Depends on

• Euler-Tour-Tree (src/DataStructure/EulerTourTree.hpp)
• メンバの有無を判定するテンプレート 他 (src/Internal/HAS_CHECK.hpp)

Verified with

• test/aoj/2235.onlinedicon.test.cpp
• test/aoj/2893.onlinedicon.test.cpp
• test/sample_test/cf_contest1140_f.test.cpp
• test/yosupo/dynamic_graph_vertex_add_component_sum.test.cpp

Code

#pragma once
#include <vector>
#include <unordered_set>
#include "src/DataStructure/EulerTourTree.hpp"
template <typename M= void, std::size_t NODE_SIZE= 4'000'000> class OnlineDynamicConnectivity {
 using T= typename EulerTourTree<M, NODE_SIZE>::T;
 using E= typename EulerTourTree<M, NODE_SIZE>::E;
 int N;
 std::vector<EulerTourTree<M, NODE_SIZE>> ett;
 std::vector<std::vector<std::unordered_set<int>>> adj;
 void replace(int x, int y, int level) {
  for (int k= 0; k < level; k++) ett[k].cut(x, y);
  for (int k= level, loop= true; k-- && loop;) {
   if (ett[k].tree_size(x) > ett[k].tree_size(y)) std::swap(x, y);
   ett[k].hilevel_edges(x, [&](int s, int d) { ett[k + 1].link(s, d, true); });
   ett[k].subedges(x, [&](int s) {
    for (auto itr= adj[k][s].begin(); itr != adj[k][s].end();) {
     auto d= *itr;
     if (adj[k][s].size() == 1) ett[k].subedge_set(s, 0);
     if (adj[k][d].size() == 1) ett[k].subedge_set(d, 0);
     adj[k][d].erase(s), itr= adj[k][s].erase(itr);
     if (ett[k].connected(s, d)) {
      if (adj[k + 1][s].size() == 0) ett[k + 1].subedge_set(s, 1);
      if (adj[k + 1][d].size() == 0) ett[k + 1].subedge_set(d, 1);
      adj[k + 1][s].insert(d), adj[k + 1][d].insert(s);
     } else {
      for (int kk= k + 1; kk--;) ett[kk].link(s, d, kk == k);
      return loop= false, true;
     }
    }
    return false;
   });
  }
 }
public:
 OnlineDynamicConnectivity(int N): N(N) { ett.emplace_back(N), adj.emplace_back(N); }
 void link(int x, int y) {
  if (ett[0].connected(x, y)) {
   if (adj[0][x].size() == 0) ett[0].subedge_set(x, 1);
   if (adj[0][y].size() == 0) ett[0].subedge_set(y, 1);
   adj[0][x].insert(y), adj[0][y].insert(x);
  } else ett[0].link(x, y, true);
 }
 void cut(int x, int y) {
  int m= ett.size();
  for (int k= 0; k < m; ++k)
   if (adj[k][x].count(y)) {
    adj[k][x].erase(y), adj[k][y].erase(x);
    if (adj[k][x].size() == 0) ett[k].subedge_set(x, 0);
    if (adj[k][y].size() == 0) ett[k].subedge_set(y, 0);
    return;
   }
  for (int k= m; k--;)
   if (ett[k].edge_exist(x, y)) {
    if (k + 1 == m) ett.emplace_back(N), adj.emplace_back(N);
    replace(x, y, k + 1);
   }
 }
 const T &operator[](int x) { return ett[0][x]; }
 const T &get(int x) { return ett[0].get(x); }
 void set(int x, T val) { ett[0].set(x, val); }
 int size(int x) { return ett[0].tree_size(x); }
 T prod(int x) { return ett[0].prod_tree(x); }
 void apply(int x, E v) { return ett[0].apply_tree(x, v); }
 bool connected(int x, int y) { return ett[0].connected(x, y); }
};

#line 2 "src/DataStructure/OnlineDynamicConnectivity.hpp"
#include <vector>
#include <unordered_set>
#line 2 "src/DataStructure/EulerTourTree.hpp"
#include <algorithm>
#include <string>
#include <unordered_map>
#include <cstddef>
#include <cstdint>
#line 2 "src/Internal/HAS_CHECK.hpp"
#include <type_traits>
#define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \
 template <class tClass> struct name##member { \
  template <class U, Dummy> static type1 check(U *); \
  static type2 check(...); \
  static tClass *mClass; \
  last; \
 }
#define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value)
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member)
#define HOGE_OR(member, name, type2) \
 MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \
 template <class tClass> using name##member##_t= typename name##member<tClass>::type
#define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t)
#define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass)
#line 8 "src/DataStructure/EulerTourTree.hpp"
template <typename M= void, size_t NODE_SIZE= 4'000'000> class EulerTourTree {
 HAS_MEMBER(op);
 HAS_MEMBER(ti);
 HAS_MEMBER(mp);
 HAS_MEMBER(cp);
 HAS_TYPE(T);
 HAS_TYPE(E);
 NULLPTR_OR(T);
 NULLPTR_OR(E);
 template <class L> static constexpr bool monoid_v= std::conjunction_v<has_T<L>, has_op<L>, has_ti<L>>;
 template <class L> static constexpr bool dual_v= std::conjunction_v<has_T<L>, has_E<L>, has_mp<L>, has_cp<L>>;
 using node_id= int;
 using vertex_id= int;
 struct Node_B {
  node_id ch[2], par;
  uint64_t flag;
 };
 template <class D, bool mo, bool du> struct Node_D: Node_B {};
 template <class D> struct Node_D<D, 1, 0>: Node_B {
  typename M::T val= M::ti(), sum= M::ti();
 };
 template <class D> struct Node_D<D, 0, 1>: Node_B {
  typename M::T val;
  typename M::E laz;
  bool laz_flg;
 };
 template <class D> struct Node_D<D, 1, 1>: Node_B {
  typename M::T val= M::ti(), sum= M::ti();
  typename M::E laz;
  bool laz_flg;
 };
 using Node= Node_D<void, monoid_v<M>, dual_v<M>>;
public:
 using T= nullptr_or_T_t<M>;
 using E= nullptr_or_E_t<M>;
private:
 static inline Node *n= new Node[NODE_SIZE];
 static inline node_id ni= 1;
 node_id new_edge(int s, int d, bool hi) {
  int i= ni++, ri= ni++;
  n[i].flag= (uint64_t(s) << 44) | (uint64_t(d) << 24) | hi;
  n[ri].flag= (uint64_t(d) << 44) | (uint64_t(s) << 24);
  return i;
 }
 static void update(node_id i) {
  n[i].flag&= 0xffffffffff00000f;
  n[i].flag|= ((n[i].flag >> 44) == ((n[i].flag >> 24) & 0xfffff)) << 4;
  n[i].flag&= -11ll, n[i].flag|= (n[i].flag << 1) & 0b1111;
  if constexpr (monoid_v<M>) n[i].sum= n[i].val;
  if (n[i].ch[0]) {
   n[i].flag+= (n[n[i].ch[0]].flag & 0xfffff0), n[i].flag|= n[n[i].ch[0]].flag & 0b1010;
   if constexpr (monoid_v<M>) n[i].sum= M::op(n[n[i].ch[0]].sum, n[i].sum);
  }
  if (n[i].ch[1]) {
   n[i].flag+= (n[n[i].ch[1]].flag & 0xfffff0), n[i].flag|= n[n[i].ch[1]].flag & 0b1010;
   if constexpr (monoid_v<M>) n[i].sum= M::op(n[i].sum, n[n[i].ch[1]].sum);
  }
 }
 static inline void map(T &v, E x, int sz) {
  if constexpr (std::is_invocable_r_v<void, decltype(M::mp), T &, E, int>) M::mp(v, x, sz);
  else M::mp(v, x);
 }
 static inline void propagate(node_id i, const E &x) {
  if (n[i].laz_flg) M::cp(n[i].laz, x);
  else n[i].laz= x, n[i].laz_flg= true;
  if ((n[i].flag >> 44) == ((n[i].flag >> 24) & 0xfffff)) map(n[i].val, x, 1);
  if constexpr (monoid_v<M>) map(n[i].sum, x, ((n[i].flag >> 4) & 0xfffff));
 }
 static inline void push(node_id i) {
  if (!n[i].laz_flg) return;
  if (n[i].ch[0]) propagate(n[i].ch[0], n[i].laz);
  if (n[i].ch[1]) propagate(n[i].ch[1], n[i].laz);
  n[i].laz_flg= false;
 }
 static inline int dir(node_id i) { return n[n[i].par].ch[1] == i; }
 static inline void rot(node_id i) {
  node_id p= n[i].par;
  int d= dir(i);
  if ((n[p].ch[d]= n[i].ch[!d])) n[n[p].ch[d]].par= p;
  n[i].ch[!d]= p;
  if ((n[i].par= n[p].par)) n[n[p].par].ch[dir(p)]= i;
  n[p].par= i, update(p);
 }
 static inline void splay(node_id i) {
  if constexpr (dual_v<M>) push(i);
  for (node_id p= n[i].par; p; rot(i), p= n[i].par) {
   node_id pp= n[p].par;
   if constexpr (dual_v<M>) {
    if (pp) push(pp);
    push(p), push(i);
   }
   if (pp) rot(dir(i) == dir(p) ? p : i);
  }
  update(i);
 }
 static inline node_id merge_back(node_id l, node_id r) {
  if (!l) return r;
  if (!r) return l;
  while (n[l].ch[1]) l= n[l].ch[1];
  return splay(l), n[n[r].par= l].ch[1]= r, update(l), l;
 }
 static inline std::pair<node_id, node_id> split(node_id i) {
  splay(i);
  node_id l= n[i].ch[0];
  return n[i].ch[0]= n[l].par= 0, update(i), std::make_pair(l, i);
 }
 static inline void reroot(node_id v) {
  auto p= split(v);
  merge_back(p.second, p.first), splay(v);
 }
 static inline bool same_root(node_id i, node_id j) {
  if (i) splay(i);
  if (j) splay(j);
  while (n[i].par) i= n[i].par;
  while (n[j].par) j= n[j].par;
  return i == j;
 }
 node_id n_st;
 std::unordered_map<uint64_t, node_id> emp;
public:
 EulerTourTree() {}
 EulerTourTree(int N): n_st(ni) {
  ni+= N;
  for (int i= 0; i < N; i++) n[i + n_st].flag= 0x100001000000 * i;
 }
 const T &operator[](vertex_id x) { return get(x); }
 const T &get(vertex_id x) {
  static_assert(monoid_v<M> || dual_v<M>, "\"get\" is not available\n");
  return n[x + n_st].val;
 }
 void set(vertex_id x, T val) {
  static_assert(monoid_v<M> || dual_v<M>, "\"set\" is not available\n");
  splay(x+= n_st), n[x].val= val, update(x);
 }
 bool edge_exist(vertex_id x, vertex_id y) {
  if (x > y) std::swap(x, y);
  return emp.count(((long long)x << 32) | y);
 }
 void link(vertex_id x, vertex_id y, bool hi= true) {
  if (x > y) std::swap(x, y);
  int ei= new_edge(x, y, hi);
  emp.insert(std::make_pair(((long long)x << 32) | y, ei));
  x+= n_st, y+= n_st, reroot(x), reroot(y);
  n[n[x].par= ei].ch[0]= x, n[n[y].par= ei].ch[1]= y;
  update(ei), merge_back(ei, ei + 1);
 }
 void cut(vertex_id x, vertex_id y) {
  if (x > y) std::swap(x, y);
  int ei= emp[((long long)x << 32) | y], rei= ei + 1;
  emp.erase(((long long)x << 32) | y);
  auto [pl, pr]= split(ei);
  node_id left, center, right;
  if (pl && same_root(pl, rei)) {
   auto [ql, qr]= split(rei);
   left= ql, center= n[qr].ch[1], right= n[pr].ch[1], n[center].par= 0;
  } else {
   splay(ei), n[ei= n[ei].ch[1]].par= 0;
   auto [ql, qr]= split(rei);
   splay(pl), left= pl, right= n[qr].ch[1];
  }
  n[right].par= 0, merge_back(left, right);
 }
 bool connected(vertex_id x, vertex_id y) { return same_root(x + n_st, y + n_st); }
 void subedge_set(vertex_id x, bool val) {
  splay(x+= n_st);
  if (val) n[x].flag|= 0b0100;
  else n[x].flag&= -5ll;
  update(x);
 }
 size_t tree_size(vertex_id x) { return splay(x+= n_st), ((n[x].flag >> 4) & 0xfffff); }
 T prod_tree(vertex_id x) {
  static_assert(monoid_v<M>, "\"prod\" is not available\n");
  return splay(x+= n_st), n[x].sum;
 }
 T prod_subtree(vertex_id x, vertex_id par= -1) {
  if (par == -1) return prod_tree(x);
  cut(x, par);
  T ret= prod_tree(x);
  link(x, par);
  return ret;
 }
 void apply_tree(vertex_id x, E v) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  splay(x+= n_st), propagate(x, v), push(x);
 }
 void apply_subtree(vertex_id x, vertex_id par, E v) { cut(x, par), apply_tree(x, v), link(x, par); }
 static std::string which_available() {
  std::string ret= "";
  if constexpr (monoid_v<M>) ret+= "\"prod\" ";
  if constexpr (dual_v<M>) ret+= "\"apply\" ";
  return ret;
 }
 template <class Func> void hilevel_edges(vertex_id v, Func f) {
  splay(v+= n_st);
  while (v && (n[v].flag & 0b0010))
   while (1) {
    if (n[v].flag & 0b0001) {
     f((n[v].flag >> 44), ((n[v].flag >> 24) & 0xfffff)), splay(v), n[v].flag&= -2ll, update(v);
     break;
    } else v= n[v].ch[!(n[v].ch[0] && (n[n[v].ch[0]].flag & 0b0010))];
   }
 }
 template <class Func> int subedges(vertex_id v, Func f) {
  splay(v+= n_st);
  while (v && (n[v].flag & 0b1000))
   for (bool loop= true; loop;) {
    if (n[v].flag & 0b0100) {
     if (f(n[v].flag >> 44)) return 1;
     splay(v), loop= false;
    } else v= n[v].ch[!(n[v].ch[0] && (n[n[v].ch[0]].flag & 0b1000))];
   }
  return 0;
 }
};
#line 5 "src/DataStructure/OnlineDynamicConnectivity.hpp"
template <typename M= void, std::size_t NODE_SIZE= 4'000'000> class OnlineDynamicConnectivity {
 using T= typename EulerTourTree<M, NODE_SIZE>::T;
 using E= typename EulerTourTree<M, NODE_SIZE>::E;
 int N;
 std::vector<EulerTourTree<M, NODE_SIZE>> ett;
 std::vector<std::vector<std::unordered_set<int>>> adj;
 void replace(int x, int y, int level) {
  for (int k= 0; k < level; k++) ett[k].cut(x, y);
  for (int k= level, loop= true; k-- && loop;) {
   if (ett[k].tree_size(x) > ett[k].tree_size(y)) std::swap(x, y);
   ett[k].hilevel_edges(x, [&](int s, int d) { ett[k + 1].link(s, d, true); });
   ett[k].subedges(x, [&](int s) {
    for (auto itr= adj[k][s].begin(); itr != adj[k][s].end();) {
     auto d= *itr;
     if (adj[k][s].size() == 1) ett[k].subedge_set(s, 0);
     if (adj[k][d].size() == 1) ett[k].subedge_set(d, 0);
     adj[k][d].erase(s), itr= adj[k][s].erase(itr);
     if (ett[k].connected(s, d)) {
      if (adj[k + 1][s].size() == 0) ett[k + 1].subedge_set(s, 1);
      if (adj[k + 1][d].size() == 0) ett[k + 1].subedge_set(d, 1);
      adj[k + 1][s].insert(d), adj[k + 1][d].insert(s);
     } else {
      for (int kk= k + 1; kk--;) ett[kk].link(s, d, kk == k);
      return loop= false, true;
     }
    }
    return false;
   });
  }
 }
public:
 OnlineDynamicConnectivity(int N): N(N) { ett.emplace_back(N), adj.emplace_back(N); }
 void link(int x, int y) {
  if (ett[0].connected(x, y)) {
   if (adj[0][x].size() == 0) ett[0].subedge_set(x, 1);
   if (adj[0][y].size() == 0) ett[0].subedge_set(y, 1);
   adj[0][x].insert(y), adj[0][y].insert(x);
  } else ett[0].link(x, y, true);
 }
 void cut(int x, int y) {
  int m= ett.size();
  for (int k= 0; k < m; ++k)
   if (adj[k][x].count(y)) {
    adj[k][x].erase(y), adj[k][y].erase(x);
    if (adj[k][x].size() == 0) ett[k].subedge_set(x, 0);
    if (adj[k][y].size() == 0) ett[k].subedge_set(y, 0);
    return;
   }
  for (int k= m; k--;)
   if (ett[k].edge_exist(x, y)) {
    if (k + 1 == m) ett.emplace_back(N), adj.emplace_back(N);
    replace(x, y, k + 1);
   }
 }
 const T &operator[](int x) { return ett[0][x]; }
 const T &get(int x) { return ett[0].get(x); }
 void set(int x, T val) { ett[0].set(x, val); }
 int size(int x) { return ett[0].tree_size(x); }
 T prod(int x) { return ett[0].prod_tree(x); }
 void apply(int x, E v) { return ett[0].apply_tree(x, v); }
 bool connected(int x, int y) { return ett[0].connected(x, y); }
};

Back to top page