Incremental Bridge-Connectivity
(data_structure/incremental_bridge_connectivity.cpp)

• View this file on GitHub
• Last update: 2020-03-12 15:47:16+09:00
• Link: https://scrapbox.io/data-structures/Incremental_Bridge-Connectivity

Depends on

• Union Find (data_structure/union_find.cpp)
• other/int_alias.cpp

Verified with

• test/incremental_bridge_connectivity.test.cpp

Code

#include "data_structure/union_find.cpp"
#include "other/int_alias.cpp"

#include <cassert>
#include <cstddef>
#include <unordered_set>
#include <utility>
#include <vector>

class incremental_bridge_connectivity {
  union_find cc;
  union_find bcc;
  std::vector<usize> bbf;

  usize size() const { return bbf.size(); }

  usize nil() const { return size(); }

  usize parent(const usize v) {
    if (bbf[v] == nil())
      return nil();
    else
      return bcc.find(bbf[v]);
  }

  usize lca(usize u, usize v) {
    std::unordered_set<usize> reached;
    while (true) {
      if (u != nil()) {
        if (!reached.insert(u).second)
          return u;
        u = parent(u);
      }
      std::swap(u, v);
    }
  }

  void condense_path(usize u, const usize v) {
    while (!bcc.same(u, v)) {
      const usize next = parent(u);
      bbf[u] = bbf[v];
      bcc.unite(u, v);
      u = next;
    }
  }

  void link(const usize x, const usize y) {
    usize v = x, prev = y;
    while (v != nil()) {
      const usize next = parent(v);
      bbf[v] = prev;
      prev = v;
      v = next;
    }
  }

public:
  incremental_bridge_connectivity() = default;

  explicit incremental_bridge_connectivity(const usize n)
      : cc(n), bcc(n), bbf(n, n) {}

  usize find_block(const usize v) {
    assert(v < size());

    return bcc.find(v);
  }

  bool bridge_connected(const usize u, const usize v) {
    assert(u < size());
    assert(v < size());

    return bcc.same(u, v);
  }

  void insert_edge(usize u, usize v) {
    assert(u < size());
    assert(v < size());

    u = bcc.find(u);
    v = bcc.find(v);
    if (cc.same(u, v)) {
      const usize w = lca(u, v);
      condense_path(u, w);
      condense_path(v, w);
    } else {
      if (cc.size(u) > cc.size(v))
        std::swap(u, v);
      link(u, v);
      cc.unite(u, v);
    }
  }
};

/**
 * @brief Incremental Bridge-Connectivity
 * @see https://scrapbox.io/data-structures/Incremental_Bridge-Connectivity
 */

#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "data_structure/union_find.cpp"

#include <cassert>
#include <utility>
#include <vector>

class union_find {
private:
  class node_type {
    friend union_find;

    usize parent;
    usize size;

    node_type(const usize parent, const usize size)
        : parent(parent), size(size) {}
  };

  std::vector<node_type> tree;

public:
  union_find() = default;

  explicit union_find(const usize n) : tree(n, node_type(n, 1)) {}

  usize size() const { return tree.size(); }

  usize find(const usize x) {
    assert(x < size());
    if (tree[x].parent == size())
      return x;
    else
      return tree[x].parent = find(tree[x].parent);
  }

  bool same(const usize x, const usize y) {
    assert(x < size());
    assert(y < size());
    return find(x) == find(y);
  }

  usize size(const usize x) {
    assert(x < size());
    return tree[find(x)].size;
  }

  void unite(usize x, usize y) {
    assert(x < size());
    assert(y < size());
    x = find(x);
    y = find(y);
    if (x != y) {
      if (tree[x].size < tree[y].size)
        std::swap(x, y);
      tree[x].size += tree[y].size;
      tree[y].parent = x;
    }
  }
};

/**
 * @brief Union Find
 * @see https://scrapbox.io/data-structures/Union_Find
 */
#line 3 "data_structure/incremental_bridge_connectivity.cpp"

#line 6 "data_structure/incremental_bridge_connectivity.cpp"
#include <unordered_set>
#line 9 "data_structure/incremental_bridge_connectivity.cpp"

class incremental_bridge_connectivity {
  union_find cc;
  union_find bcc;
  std::vector<usize> bbf;

  usize size() const { return bbf.size(); }

  usize nil() const { return size(); }

  usize parent(const usize v) {
    if (bbf[v] == nil())
      return nil();
    else
      return bcc.find(bbf[v]);
  }

  usize lca(usize u, usize v) {
    std::unordered_set<usize> reached;
    while (true) {
      if (u != nil()) {
        if (!reached.insert(u).second)
          return u;
        u = parent(u);
      }
      std::swap(u, v);
    }
  }

  void condense_path(usize u, const usize v) {
    while (!bcc.same(u, v)) {
      const usize next = parent(u);
      bbf[u] = bbf[v];
      bcc.unite(u, v);
      u = next;
    }
  }

  void link(const usize x, const usize y) {
    usize v = x, prev = y;
    while (v != nil()) {
      const usize next = parent(v);
      bbf[v] = prev;
      prev = v;
      v = next;
    }
  }

public:
  incremental_bridge_connectivity() = default;

  explicit incremental_bridge_connectivity(const usize n)
      : cc(n), bcc(n), bbf(n, n) {}

  usize find_block(const usize v) {
    assert(v < size());

    return bcc.find(v);
  }

  bool bridge_connected(const usize u, const usize v) {
    assert(u < size());
    assert(v < size());

    return bcc.same(u, v);
  }

  void insert_edge(usize u, usize v) {
    assert(u < size());
    assert(v < size());

    u = bcc.find(u);
    v = bcc.find(v);
    if (cc.same(u, v)) {
      const usize w = lca(u, v);
      condense_path(u, w);
      condense_path(v, w);
    } else {
      if (cc.size(u) > cc.size(v))
        std::swap(u, v);
      link(u, v);
      cc.unite(u, v);
    }
  }
};

/**
 * @brief Incremental Bridge-Connectivity
 * @see https://scrapbox.io/data-structures/Incremental_Bridge-Connectivity
 */

Back to top page