proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: Lowlink (tools/lowlink.hpp)

Given an undirected graph, it creates a data structure that allows enumeration of bridges and articulation points in linear time. The graph may contain self-loops and multiple edges, and need not be connected.

License

Author

Constructor

lowlink graph(int n);

It creates an undirected graph with $n$ vertices and $0$ edges.

Constraints

Time Complexity

size

int graph.size();

It returns $n$.

Constraints

Time Complexity

add_edge

int graph.add_edge(int u, int v);

It adds an undirected edge connecting vertex $u$ and vertex $v$ to the graph, and returns the number of edges that existed before the undirected edge was added.

Constraints

Time Complexity

get_edge

struct edge {
  int from;
  int to;
};
const edge& graph.get_edge(int k);

It returns information about the $k$-th edge in $0$-indexed. The information means that the $k$-th edge added to this graph is the undirected edge connecting vertex from and vertex to. Of course, as this is an undirected graph, the from and to orientations are meaningless. In an undirected graph such as this graph, the vertex numbers are always sorted so that from $\leq$ to.

Constraints

Time Complexity

edges

(1)

const std::vector<edge>& graph.edges();

It returns all the edges in the graph. The edges are ordered in the same order as added by add_edge.

Constraints

Time Complexity

(2)

struct edges_iterable {
  struct iterator {
    const edge& operator*();
    iterator& operator++();
    iterator operator++(int):
    friend bool operator==(iterator lhs, iterator rhs);
    friend bool operator!=(iterator lhs, iterator rhs);
  };
  iterator begin();
  iterator end();
};
edges_iterable graph.edges(int v);

It returns an iterator that enumerates the edges adjacent to vertex $v$. The enumeration order is undefined, except that each element appears exactly once.

Constraints

Time Complexity

neighbors

struct neighbors_iterable {
  struct iterator {
    int operator*();
    iterator& operator++();
    iterator operator++(int):
    friend bool operator==(iterator lhs, iterator rhs);
    friend bool operator!=(iterator lhs, iterator rhs);
  };
  iterator begin();
  iterator end();
};
neighbors_iterable graph.neighbors(int v);

It returns an iterator that enumerates the vertices adjacent to vertex $v$. The enumeration order is undefined. If the graph contains multiple edges, a vertex may appear more than once. Also, if the graph contains self-loops, vertex $v$ itself may appear in the enumeration.

Constraints

Time Complexity

build

void graph.build();

It creates a data structure that allows bridges and articulation points to be enumerated in linear time. The key elements are values called $\mathrm{ord}(v)$ and $\mathrm{low}(v)$ assigned to each vertex $v$, which are defined as follows.

We first repeat the process of creating a spanning tree for each connected component of the graph by a depth-first search, choosing the roots as appropriate. We call this spanning tree a DFS tree, and the edges belonging to the DFS tree are called tree edges. We regard a tree edge as a directed edge from the root side to the leaf side.

We also refer to edges that do not belong to the DFS tree as back edges. Back edges are known to have both endpoints always in an ancestor-descendant relationship. We regard a back edge as a directed edge from the leaf side to the root side.

We define $\mathrm{ord}(v)$ and $\mathrm{low}(v)$ as values determined for each vertex $v$ of the spanning tree. The definition of $\mathrm{ord}(v)$ is the pre-ordered vertex number of the DFS tree. The $\mathrm{ord}(r)$ of root $r$ is $0$. The definition of $\mathrm{low}(v)$ is $\displaystyle \min_{s \in S}\left(\mathrm{ord}\left(s\right)\right)$, where $S$ is the set of vertices reachable from vertex $v$ using zero or more tree edges and one or less back edges.

Note that there are as many vertices $v$ such that $\mathrm{ord}(v) = 0$ as there are connected components.

Constraints

Time Complexity

vparent

int graph.vparent(int v);

It returns $u$ such that the parent of vertex $v$ in the DFS tree is vertex $u$.

Constraints

Time Complexity

eparent

const edge& graph.eparent(int v);

It returns the tree edge towards vertex $v$.

Constraints

Time Complexity

vchildren

struct vchildren_iterable {
  struct iterator {
    int operator*();
    iterator& operator++();
    iterator operator++(int):
    friend bool operator==(iterator lhs, iterator rhs);
    friend bool operator!=(iterator lhs, iterator rhs);
  };
  iterator begin();
  iterator end();
};
vchildren_iterable graph.vchildren(int v);

It returns $u$ such that the parent of vertex $u$ in the DFS tree is vertex $v$.

Constraints

Time Complexity

echildren

struct echildren_iterable {
  struct iterator {
    const edge& operator*();
    iterator& operator++();
    iterator operator++(int):
    friend bool operator==(iterator lhs, iterator rhs);
    friend bool operator!=(iterator lhs, iterator rhs);
  };
  iterator begin();
  iterator end();
};
echildren_iterable graph.echildren(int v);

It returns the tree edges outward from vertex $v$.

Constraints

Time Complexity

ord

int graph.ord(int v);

It returns $\mathrm{ord}(v)$.

Constraints

Time Complexity

low

int graph.low(int v);

It returns $\mathrm{low}(v)$.

Constraints

Time Complexity

ncc

int graph.ncc();

It returns the number of connected components of the graph.

Constraints

Time Complexity

ncc_without_vertex

int graph.ncc_without_vertex(int v);

It returns the number of connected components of the graph without vertex $v$.

Constraints

Time Complexity

is_articulation_point

bool graph.is_articulation_point(int v);

It returns whether vertex $v$ is an articulation point or not.

Constraints

Time Complexity

is_bridge

bool graph.is_bridge(int k);

It returns whether the $k$-th edge is a bridge or not.

Constraints

Time Complexity

biconnected_components

std::vector<std::vector<int>> graph.biconnected_components();

It divides the graph into biconnected components and returns the list of them.

More precisely, it returns the list of the “list of the vertices in a biconnected component”. Both of the orders of the biconnected components and the vertices are undefined.

Constraints

Time Complexity

Depends on

Verified with

Code

#ifndef TOOLS_LOWLINK_HPP
#define TOOLS_LOWLINK_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
#include "tools/chmin.hpp"
#include "tools/fix.hpp"
#include "tools/less_by.hpp"

namespace tools {
  class lowlink {
  public:
    struct edge {
      int from;
      int to;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<int>> m_graph;
    bool m_built;
    ::std::vector<int> m_from;
    ::std::vector<int> m_ord;
    ::std::vector<int> m_low;
    int m_ncc;
    ::std::vector<int> m_ncc_without_vertex;

  public:
    class neighbors_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = int;
        using reference = const int&;
        using pointer = const int*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
        }

        value_type operator*() const {
          const auto& edge = this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
          return edge.from ^ edge.to ^ this->m_v;
        }
        iterator& operator++() {
          ++this->m_i;
          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      neighbors_iterable() = default;
      neighbors_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    class edges_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = edge;
        using reference = const edge&;
        using pointer = const edge*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
        }

        reference operator*() const {
          return this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
        }
        iterator& operator++() {
          ++this->m_i;
          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      edges_iterable() = default;
      edges_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    class vchildren_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = int;
        using reference = const int&;
        using pointer = const int*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          for (; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);
        }

        value_type operator*() const {
          const auto& edge = this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
          return edge.from ^ edge.to ^ this->m_v;
        }
        iterator& operator++() {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          assert(this->m_i < eids.size());

          for (++this->m_i; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);

          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      vchildren_iterable() = default;
      vchildren_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    class echildren_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = edge;
        using reference = const edge&;
        using pointer = const edge*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          for (; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);
        }

        reference operator*() const {
          return this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
        }
        iterator& operator++() {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          assert(this->m_i < eids.size());

          for (++this->m_i; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);

          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      echildren_iterable() = default;
      echildren_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    lowlink() = default;
    explicit lowlink(const int n) : m_graph(n), m_built(false) {
    }

    int size() const {
      return this->m_graph.size();
    }

    int add_edge(int u, int v) {
      assert(!this->m_built);
      assert(0 <= u && u < this->size());
      assert(0 <= v && v < this->size());
      ::std::tie(u, v) = ::std::minmax({u, v});
      this->m_edges.push_back(edge{u, v});
      this->m_graph[u].push_back(this->m_edges.size() - 1);
      this->m_graph[v].push_back(this->m_edges.size() - 1);
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const int k) const {
      assert(0 <= k && k < this->m_edges.size());
      return this->m_edges[k];
    }

    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

    neighbors_iterable neighbors(const int v) const {
      assert(0 <= v && v < this->size());
      return neighbors_iterable(this, v);
    }

    edges_iterable edges(const int v) const {
      assert(0 <= v && v < this->size());
      return edges_iterable(this, v);
    }

    void build() {
      assert(!this->m_built);
      this->m_built = true;

      const auto N_A = -1;

      this->m_from.assign(this->size(), N_A);
      this->m_ord.assign(this->size(), N_A);
      this->m_low.assign(this->size(), N_A);
      this->m_ncc = 0;

      for (int r = 0; r < this->size(); ++r) {
        if (this->m_ord[r] != N_A) continue;

        ++this->m_ncc;
        int next_ord = 0;

        ::std::stack<::std::pair<int, int>> stack;
        stack.emplace(r, N_A);
        stack.emplace(r, N_A - 1);
        while (!stack.empty()) {
          const auto [v, from] = stack.top();
          stack.pop();

          if (from != N_A) {
            if (this->m_ord[v] != N_A) continue;

            this->m_from[v] = from;
            this->m_ord[v] = next_ord++;

            for (const auto eid : this->m_graph[v]) {
              const auto& edge = this->m_edges[eid];
              const auto u = edge.from ^ edge.to ^ v;
              if (this->m_ord[u] != N_A) continue;

              stack.emplace(u, N_A);
              stack.emplace(u, eid);
            }
          } else {
            if (this->m_low[v] != N_A) continue;

            this->m_low[v] = this->m_ord[v];
            for (const auto eid : this->m_graph[v]) {
              const auto& edge = this->m_edges[eid];
              const auto u = edge.from ^ edge.to ^ v;
              if (this->m_ord[u] < this->m_ord[v] && eid != this->m_from[v]) {
                ::tools::chmin(this->m_low[v], this->m_ord[u]);
              } else if (this->m_ord[u] > this->m_ord[v] && eid == this->m_from[u]) {
                ::tools::chmin(this->m_low[v], this->m_low[u]);
              }
            }
          }
        }

        this->m_from[r] = N_A;
      }

      this->m_ncc_without_vertex.assign(this->size(), this->m_ncc);
      for (int v = 0; v < this->size(); ++v) {
        if (this->m_ord[v] == 0) {
          this->m_ncc_without_vertex[v] += ::std::distance(this->echildren(v).begin(), this->echildren(v).end());
          --this->m_ncc_without_vertex[v];
        } else {
          for (const auto& edge : this->echildren(v)) {
            const auto u = edge.from ^ edge.to ^ v;
            if (this->m_ord[v] <= this->m_low[u]) {
              ++this->m_ncc_without_vertex[v];
            }
          }
        }
      }
    }

    int vparent(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());
      assert(this->m_ord[v] > 0);

      const auto& edge = this->m_edges[this->m_from[v]];
      return edge.from ^ edge.to ^ v;
    }

    const edge& eparent(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());
      assert(this->m_ord[v] > 0);

      return this->m_edges[this->m_from[v]];
    }

    vchildren_iterable vchildren(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return vchildren_iterable(this, v);
    }

    echildren_iterable echildren(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return echildren_iterable(this, v);
    }

    int ord(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_ord[v];
    }

    int low(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_low[v];
    }

    int ncc() const {
      assert(this->m_built);

      return this->m_ncc;
    }

    int ncc_without_vertex(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_ncc_without_vertex[v];
    }

    bool is_articulation_point(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_ncc_without_vertex[v] > this->m_ncc;
    }

    bool is_bridge(const int k) const {
      assert(this->m_built);
      assert(0 <= k && k < this->m_edges.size());

      const auto [u, v] = ::std::minmax({this->m_edges[k].from, this->m_edges[k].to}, ::tools::less_by([&](const auto w) { return this->m_ord[w]; }));
      return this->m_ord[u] < this->m_low[v];
    }

    ::std::vector<::std::vector<int>> biconnected_components() const {
      assert(this->m_built);

      ::std::vector<::std::vector<int>> groups;

      for (int r = 0; r < this->size(); ++r) {
        if (this->ord(r) == 0) {
          if (this->m_ncc_without_vertex[r] < this->m_ncc) {
            groups.emplace_back(::std::initializer_list<int>{r});
          } else {
            ::tools::fix([&](auto&& dfs, const auto g, const auto v) -> void {
              for (const auto u : this->vchildren(v)) {
                if (this->ord(v) <= this->low(u)) {
                  groups.emplace_back(::std::initializer_list<int>{v, u});
                  dfs(groups.size() - 1, u);
                } else {
                  groups[g].push_back(u);
                  dfs(g, u);
                }
              }
            })(-1, r);
          }
        }
      }

      return groups;
    }
  };
}

#endif

#line 1 "tools/lowlink.hpp"



#include <algorithm>
#include <cassert>
#include <cstddef>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
#line 1 "tools/chmin.hpp"



#include <type_traits>
#line 6 "tools/chmin.hpp"

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/fix.hpp"



#line 6 "tools/fix.hpp"

namespace tools {
  template <typename F>
  struct fix : F {
    template <typename G>
    fix(G&& g) : F({::std::forward<G>(g)}) {
    }

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {
      return F::operator()(*this, ::std::forward<Args>(args)...);
    }
  };

  template <typename F>
  fix(F&&) -> fix<::std::decay_t<F>>;
}


#line 1 "tools/less_by.hpp"



namespace tools {

  template <class F>
  class less_by {
  private:
    F selector;

  public:
    less_by(const F& selector) : selector(selector) {
    }

    template <class T>
    bool operator()(const T& x, const T& y) const {
      return selector(x) < selector(y);
    }
  };
}


#line 17 "tools/lowlink.hpp"

namespace tools {
  class lowlink {
  public:
    struct edge {
      int from;
      int to;
    };

  private:
    ::std::vector<edge> m_edges;
    ::std::vector<::std::vector<int>> m_graph;
    bool m_built;
    ::std::vector<int> m_from;
    ::std::vector<int> m_ord;
    ::std::vector<int> m_low;
    int m_ncc;
    ::std::vector<int> m_ncc_without_vertex;

  public:
    class neighbors_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = int;
        using reference = const int&;
        using pointer = const int*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
        }

        value_type operator*() const {
          const auto& edge = this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
          return edge.from ^ edge.to ^ this->m_v;
        }
        iterator& operator++() {
          ++this->m_i;
          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      neighbors_iterable() = default;
      neighbors_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    class edges_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = edge;
        using reference = const edge&;
        using pointer = const edge*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
        }

        reference operator*() const {
          return this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
        }
        iterator& operator++() {
          ++this->m_i;
          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      edges_iterable() = default;
      edges_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    class vchildren_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = int;
        using reference = const int&;
        using pointer = const int*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          for (; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);
        }

        value_type operator*() const {
          const auto& edge = this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
          return edge.from ^ edge.to ^ this->m_v;
        }
        iterator& operator++() {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          assert(this->m_i < eids.size());

          for (++this->m_i; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);

          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      vchildren_iterable() = default;
      vchildren_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    class echildren_iterable {
    private:
      ::tools::lowlink const *m_parent;
      int m_v;

    public:
      class iterator {
      private:
        ::tools::lowlink const *m_parent;
        int m_v;
        int m_i;

      public:
        using difference_type = ::std::ptrdiff_t;
        using value_type = edge;
        using reference = const edge&;
        using pointer = const edge*;
        using iterator_category = ::std::input_iterator_tag;

        iterator() = default;
        iterator(::tools::lowlink const * const parent, const int v, const int i) : m_parent(parent), m_v(v), m_i(i) {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          for (; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);
        }

        reference operator*() const {
          return this->m_parent->m_edges[this->m_parent->m_graph[this->m_v][this->m_i]];
        }
        iterator& operator++() {
          const auto& eids = this->m_parent->m_graph[this->m_v];
          assert(this->m_i < eids.size());

          for (++this->m_i; this->m_i < eids.size() && [&]() {
            const auto eid = eids[this->m_i];
            const auto& edge = this->m_parent->m_edges[eid];
            return this->m_parent->m_from[edge.from ^ edge.to ^ this->m_v] != eid;
          }(); ++this->m_i);

          return *this;
        }
        iterator operator++(int) {
          const auto self = *this;
          ++*this;
          return self;
        }
        friend bool operator==(const iterator& lhs, const iterator& rhs) {
          assert(lhs.m_parent == rhs.m_parent);
          assert(lhs.m_v == rhs.m_v);
          return lhs.m_i == rhs.m_i;
        }
        friend bool operator!=(const iterator& lhs, const iterator& rhs) {
          return !(lhs == rhs);
        }
      };

      echildren_iterable() = default;
      echildren_iterable(::tools::lowlink const * const parent, const int v) : m_parent(parent), m_v(v) {
      }

      iterator begin() const {
        return iterator(this->m_parent, this->m_v, 0);
      };
      iterator end() const {
        return iterator(this->m_parent, this->m_v, this->m_parent->m_graph[this->m_v].size());
      }
    };

    lowlink() = default;
    explicit lowlink(const int n) : m_graph(n), m_built(false) {
    }

    int size() const {
      return this->m_graph.size();
    }

    int add_edge(int u, int v) {
      assert(!this->m_built);
      assert(0 <= u && u < this->size());
      assert(0 <= v && v < this->size());
      ::std::tie(u, v) = ::std::minmax({u, v});
      this->m_edges.push_back(edge{u, v});
      this->m_graph[u].push_back(this->m_edges.size() - 1);
      this->m_graph[v].push_back(this->m_edges.size() - 1);
      return this->m_edges.size() - 1;
    }

    const edge& get_edge(const int k) const {
      assert(0 <= k && k < this->m_edges.size());
      return this->m_edges[k];
    }

    const ::std::vector<edge>& edges() const {
      return this->m_edges;
    }

    neighbors_iterable neighbors(const int v) const {
      assert(0 <= v && v < this->size());
      return neighbors_iterable(this, v);
    }

    edges_iterable edges(const int v) const {
      assert(0 <= v && v < this->size());
      return edges_iterable(this, v);
    }

    void build() {
      assert(!this->m_built);
      this->m_built = true;

      const auto N_A = -1;

      this->m_from.assign(this->size(), N_A);
      this->m_ord.assign(this->size(), N_A);
      this->m_low.assign(this->size(), N_A);
      this->m_ncc = 0;

      for (int r = 0; r < this->size(); ++r) {
        if (this->m_ord[r] != N_A) continue;

        ++this->m_ncc;
        int next_ord = 0;

        ::std::stack<::std::pair<int, int>> stack;
        stack.emplace(r, N_A);
        stack.emplace(r, N_A - 1);
        while (!stack.empty()) {
          const auto [v, from] = stack.top();
          stack.pop();

          if (from != N_A) {
            if (this->m_ord[v] != N_A) continue;

            this->m_from[v] = from;
            this->m_ord[v] = next_ord++;

            for (const auto eid : this->m_graph[v]) {
              const auto& edge = this->m_edges[eid];
              const auto u = edge.from ^ edge.to ^ v;
              if (this->m_ord[u] != N_A) continue;

              stack.emplace(u, N_A);
              stack.emplace(u, eid);
            }
          } else {
            if (this->m_low[v] != N_A) continue;

            this->m_low[v] = this->m_ord[v];
            for (const auto eid : this->m_graph[v]) {
              const auto& edge = this->m_edges[eid];
              const auto u = edge.from ^ edge.to ^ v;
              if (this->m_ord[u] < this->m_ord[v] && eid != this->m_from[v]) {
                ::tools::chmin(this->m_low[v], this->m_ord[u]);
              } else if (this->m_ord[u] > this->m_ord[v] && eid == this->m_from[u]) {
                ::tools::chmin(this->m_low[v], this->m_low[u]);
              }
            }
          }
        }

        this->m_from[r] = N_A;
      }

      this->m_ncc_without_vertex.assign(this->size(), this->m_ncc);
      for (int v = 0; v < this->size(); ++v) {
        if (this->m_ord[v] == 0) {
          this->m_ncc_without_vertex[v] += ::std::distance(this->echildren(v).begin(), this->echildren(v).end());
          --this->m_ncc_without_vertex[v];
        } else {
          for (const auto& edge : this->echildren(v)) {
            const auto u = edge.from ^ edge.to ^ v;
            if (this->m_ord[v] <= this->m_low[u]) {
              ++this->m_ncc_without_vertex[v];
            }
          }
        }
      }
    }

    int vparent(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());
      assert(this->m_ord[v] > 0);

      const auto& edge = this->m_edges[this->m_from[v]];
      return edge.from ^ edge.to ^ v;
    }

    const edge& eparent(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());
      assert(this->m_ord[v] > 0);

      return this->m_edges[this->m_from[v]];
    }

    vchildren_iterable vchildren(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return vchildren_iterable(this, v);
    }

    echildren_iterable echildren(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return echildren_iterable(this, v);
    }

    int ord(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_ord[v];
    }

    int low(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_low[v];
    }

    int ncc() const {
      assert(this->m_built);

      return this->m_ncc;
    }

    int ncc_without_vertex(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_ncc_without_vertex[v];
    }

    bool is_articulation_point(const int v) const {
      assert(this->m_built);
      assert(0 <= v && v < this->size());

      return this->m_ncc_without_vertex[v] > this->m_ncc;
    }

    bool is_bridge(const int k) const {
      assert(this->m_built);
      assert(0 <= k && k < this->m_edges.size());

      const auto [u, v] = ::std::minmax({this->m_edges[k].from, this->m_edges[k].to}, ::tools::less_by([&](const auto w) { return this->m_ord[w]; }));
      return this->m_ord[u] < this->m_low[v];
    }

    ::std::vector<::std::vector<int>> biconnected_components() const {
      assert(this->m_built);

      ::std::vector<::std::vector<int>> groups;

      for (int r = 0; r < this->size(); ++r) {
        if (this->ord(r) == 0) {
          if (this->m_ncc_without_vertex[r] < this->m_ncc) {
            groups.emplace_back(::std::initializer_list<int>{r});
          } else {
            ::tools::fix([&](auto&& dfs, const auto g, const auto v) -> void {
              for (const auto u : this->vchildren(v)) {
                if (this->ord(v) <= this->low(u)) {
                  groups.emplace_back(::std::initializer_list<int>{v, u});
                  dfs(groups.size() - 1, u);
                } else {
                  groups[g].push_back(u);
                  dfs(g, u);
                }
              }
            })(-1, r);
          }
        }
      }

      return groups;
    }
  };
}
Back to top page