cp-library

C++ Library for Competitive Programming

View the Project on GitHub emthrm/cp-library

:warning: グラフ/二重辺連結成分分解 lowlink 版
(test/graph/2-edge-connected_components_by_lowlink.test.cpp)

Depends on

Code

/*
 * @title グラフ/二重辺連結成分分解 lowlink 版
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/arc039/tasks/arc039_d
 */

#include <iostream>
#include <vector>

#include "emthrm/graph/2-edge-connected_components_by_lowlink.hpp"
#include "emthrm/graph/edge.hpp"
#include "emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  while (m--) {
    int x, y;
    std::cin >> x >> y;
    --x; --y;
    graph[x].emplace_back(x, y, 1);
    graph[y].emplace_back(y, x, 1);
  }
  const emthrm::TwoEdgeConnectedComponents<int>
      two_edge_connected_components(graph);
  emthrm::LowestCommonAncestorByDoubling<int>
      lca(two_edge_connected_components.g);
  lca.build();
  int q;
  std::cin >> q;
  while (q--) {
    int a, b, c;
    std::cin >> a >> b >> c;
    --a; --b; --c;
    a = two_edge_connected_components.id[a];
    b = two_edge_connected_components.id[b];
    c = two_edge_connected_components.id[c];
    if (lca.distance(a, b) + lca.distance(b, c) == lca.distance(a, c)) {
      std::cout << "OK\n";
    } else {
      std::cout << "NG\n";
    }
  }
  return 0;
}
#line 1 "test/graph/2-edge-connected_components_by_lowlink.test.cpp"
/*
 * @title グラフ/二重辺連結成分分解 lowlink 版
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/arc039/tasks/arc039_d
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/graph/2-edge-connected_components_by_lowlink.hpp"



// #include <algorithm>
#include <ranges>
#line 7 "include/emthrm/graph/2-edge-connected_components_by_lowlink.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/lowlink.hpp"



#include <algorithm>
#line 6 "include/emthrm/graph/lowlink.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 8 "include/emthrm/graph/lowlink.hpp"

namespace emthrm {

template <typename CostType>
struct Lowlink {
  std::vector<int> order, lowlink, articulation_points;
  std::vector<Edge<CostType>> bridges;
  const std::vector<std::vector<Edge<CostType>>> graph;

  explicit Lowlink(const std::vector<std::vector<Edge<CostType>>>& graph)
      : graph(graph) {
    const int n = graph.size();
    order.assign(n, -1);
    lowlink.resize(n);
    int t = 0;
    for (int i = 0; i < n; ++i) {
      if (order[i] == -1) dfs(-1, i, &t);
    }
  }

 private:
  void dfs(const int par, const int ver, int* t) {
    order[ver] = lowlink[ver] = (*t)++;
    int num = 0;
    bool is_articulation_point = false;
    for (const Edge<CostType>& e : graph[ver]) {
      if (order[e.dst] == -1) {
        ++num;
        dfs(ver, e.dst, t);
        lowlink[ver] = std::min(lowlink[ver], lowlink[e.dst]);
        if (order[ver] <= lowlink[e.dst]) {
          is_articulation_point = true;
          if (order[ver] < lowlink[e.dst]) {
            bridges.emplace_back(std::min(ver, e.dst), std::max(ver, e.dst),
                                 e.cost);
          }
        }
      } else if (e.dst != par) {
        lowlink[ver] = std::min(lowlink[ver], order[e.dst]);
      }
    }
    if ((par == -1 && num >= 2) || (par != -1 && is_articulation_point)) {
      articulation_points.emplace_back(ver);
    }
  }
};

}  // namespace emthrm


#line 10 "include/emthrm/graph/2-edge-connected_components_by_lowlink.hpp"

namespace emthrm {

template <typename CostType, bool IS_FULL_VER = false>
struct TwoEdgeConnectedComponents : Lowlink<CostType> {
  std::vector<int> id;
  std::vector<std::vector<int>> vertices;
  std::vector<std::vector<Edge<CostType>>> g;

  explicit TwoEdgeConnectedComponents(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : Lowlink<CostType>(graph) {
    const int n = graph.size();
    id.assign(n, -1);
    int m = 0;
    for (int i = 0; i < n; ++i) {
      if (id[i] == -1) dfs(-1, i, &m);
    }
    g.resize(m);
    for (const Edge<CostType>& e : this->bridges) {
      const int u = id[e.src], v = id[e.dst];
      g[u].emplace_back(u, v, e.cost);
      g[v].emplace_back(v, u, e.cost);
    }
    // if constexpr (IS_FULL_VER) {
    //   for (int i = 0; i < m; ++i) {
    //     std::sort(vertices[i].begin(), vertices[i].end());
    //   }
    // }
  }

 private:
  void dfs(const int par, const int ver, int* m) {
    if (par != -1 && this->order[par] >= this->lowlink[ver]) {
      id[ver] = id[par];
    } else {
      id[ver] = (*m)++;
      if constexpr (IS_FULL_VER) vertices.emplace_back();
    }
    if constexpr (IS_FULL_VER) vertices[id[ver]].emplace_back(ver);
    for (const int e : this->graph[ver]
                     | std::views::transform(&Edge<CostType>::dst)) {
      if (id[e] == -1) dfs(ver, e, m);
    }
  }
};

}  // namespace emthrm


#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 1 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"



#include <bit>
#include <cassert>
#include <utility>
#line 8 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 10 "include/emthrm/graph/tree/lowest_common_ancestor_by_doubling.hpp"

namespace emthrm {

template <typename CostType>
struct LowestCommonAncestorByDoubling {
  std::vector<int> depth;
  std::vector<CostType> dist;

  explicit LowestCommonAncestorByDoubling(
      const std::vector<std::vector<Edge<CostType>>>& graph)
      : is_built(false), n(graph.size()),
        table_h(std::countr_zero(std::bit_floor(graph.size())) + 1),
        graph(graph) {
    assert(n > 0);
    depth.resize(n);
    dist.resize(n);
    parent.resize(table_h, std::vector<int>(n));
  }

  void build(const int root = 0) {
    is_built = true;
    dfs(-1, root, 0, 0);
    for (int i = 0; i + 1 < table_h; ++i) {
      for (int ver = 0; ver < n; ++ver) {
        parent[i + 1][ver] =
            (parent[i][ver] == -1 ? -1 : parent[i][parent[i][ver]]);
      }
    }
  }

  int query(int u, int v) const {
    assert(is_built);
    if (depth[u] > depth[v]) std::swap(u, v);
    for (int i = 0; i < table_h; ++i) {
      if ((depth[v] - depth[u]) >> i & 1) v = parent[i][v];
    }
    if (u == v) return u;
    for (int i = table_h - 1; i >= 0; --i) {
      if (parent[i][u] != parent[i][v]) {
        u = parent[i][u];
        v = parent[i][v];
      }
    }
    return parent.front()[u];
  }

  CostType distance(const int u, const int v) const {
    assert(is_built);
    return dist[u] + dist[v] - dist[query(u, v)] * 2;
  }

  int level_ancestor(int v, const int d) const {
    assert(is_built);
    if (depth[v] < d) return -1;
    for (int i = depth[v] - d, bit = 0; i > 0; i >>= 1, ++bit) {
      if (i & 1) v = parent[bit][v];
    }
    return v;
  }

 private:
  bool is_built;
  const int n, table_h;
  std::vector<std::vector<int>> parent;
  const std::vector<std::vector<Edge<CostType>>> graph;

  void dfs(const int par, const int ver, const int cur_depth,
           const CostType cur_dist) {
    depth[ver] = cur_depth;
    dist[ver] = cur_dist;
    parent.front()[ver] = par;
    for (const Edge<CostType>& e : graph[ver]) {
      if (e.dst != par) dfs(ver, e.dst, cur_depth + 1, cur_dist + e.cost);
    }
  }
};

}  // namespace emthrm


#line 14 "test/graph/2-edge-connected_components_by_lowlink.test.cpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  while (m--) {
    int x, y;
    std::cin >> x >> y;
    --x; --y;
    graph[x].emplace_back(x, y, 1);
    graph[y].emplace_back(y, x, 1);
  }
  const emthrm::TwoEdgeConnectedComponents<int>
      two_edge_connected_components(graph);
  emthrm::LowestCommonAncestorByDoubling<int>
      lca(two_edge_connected_components.g);
  lca.build();
  int q;
  std::cin >> q;
  while (q--) {
    int a, b, c;
    std::cin >> a >> b >> c;
    --a; --b; --c;
    a = two_edge_connected_components.id[a];
    b = two_edge_connected_components.id[b];
    c = two_edge_connected_components.id[c];
    if (lca.distance(a, b) + lca.distance(b, c) == lca.distance(a, c)) {
      std::cout << "OK\n";
    } else {
      std::cout << "NG\n";
    }
  }
  return 0;
}
Back to top page