C++ Library for Competitive Programming
/*
* @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;
}