Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
ARC039D
#include <algorithm>
#include <utility>
#include <vector>
using Graph = std::vector<std::vector<int>>;
using Edge = std::pair<int, int>;
class BridgeHelper {
const Graph& graph;
std::vector<int> ord, low;
int k = 0;
public:
std::vector<Edge> bridges;
BridgeHelper(const Graph& graph) : graph(graph), ord(graph.size(), -1), low(graph.size()) {
for (int u = 0; u < graph.size(); ++u) {
if (ord[u] >= 0) continue;
dfs(u);
}
}
bool is_bridge(int u, int v) const {
if (ord[u] > ord[v]) std::swap(u, v);
return ord[u] < low[v];
}
private:
void dfs(int u, int p = -1) {
ord[u] = low[u] = k;
++k;
for (int v : graph[u]) {
if (v == p) continue;
if (ord[v] >= 0) {
low[u] = std::min(low[u], ord[v]);
} else {
dfs(v, u);
low[u] = std::min(low[u], low[v]);
}
if (is_bridge(u, v)) bridges.emplace_back(u, v);
}
}
};
struct BICC {
std::vector<std::vector<int>> comps;
std::vector<int> belongs;
const BridgeHelper bridge_helper;
private:
const Graph& graph;
public:
BICC(const Graph& graph) : graph(graph), bridge_helper(graph), belongs(graph.size(), -1) {
for (const auto& bridge : bridge_helper.bridges) {
add_component(bridge.first);
add_component(bridge.second);
}
add_component(0);
}
Graph to_tree() const {
Graph tree(comps.size());
for (const auto& bridge : bridge_helper.bridges) {
int u = belongs[bridge.first], v = belongs[bridge.second];
tree[u].emplace_back(v);
tree[v].emplace_back(u);
}
return tree;
}
private:
void fill_component(int c, int u) {
comps[c].emplace_back(u);
belongs[u] = c;
for (int v : graph[u]) {
if (belongs[v] >= 0) continue;
if (bridge_helper.is_bridge(u, v)) continue;
fill_component(c, v);
}
}
void add_component(int u) {
if (belongs[u] >= 0) return;
comps.emplace_back();
fill_component(comps.size() - 1, u);
}
};
constexpr int roundup_log2(int x, int a = 1, int k = 0) {
return a < x ? roundup_log2(x, a + a, k + 1) : std::max(k, 1);
}
struct LCA {
private:
const Graph& tree;
const int root;
std::vector<int> depth;
std::vector<std::vector<int>> parent;
public:
LCA(const Graph& tree, int root)
: tree(tree), root(root), depth(tree.size()),
parent(roundup_log2(tree.size()), std::vector<int>(tree.size())) {
build(root);
for (int k = 0; k + 1 < parent.size(); ++k) {
for (int u = 0; u < tree.size(); ++u) {
if (parent[k][u] < 0) {
parent[k + 1][u] = -1;
} else {
parent[k + 1][u] = parent[k][parent[k][u]];
}
}
}
}
int query(int u, int v) const {
if (depth[u] > depth[v]) std::swap(u, v);
for (int k = 0; k < parent.size(); ++k) {
if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
}
if (u == v) return u;
for (int k = parent.size() - 1; k >= 0; --k) {
if (parent[k][u] == parent[k][v]) continue;
u = parent[k][u];
v = parent[k][v];
}
return parent[0][u];
}
int dist(int u, int v) const { return depth[u] + depth[v] - 2 * depth[query(u, v)]; }
private:
void build(int u, int p = -1, int d = 0) {
parent[0][u] = p;
depth[u] = d;
for (int v : tree[u]) {
if (v == p) continue;
build(v, u, d + 1);
}
}
};
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
inline int in() {
int x;
scanf("%d", &x);
return x;
}
int main() {
int N = in(), M = in();
Graph G(N);
rep(i, M) {
int u = in() - 1, v = in() - 1;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
BICC bicc(G);
Graph tree = bicc.to_tree();
LCA lca(tree, 0);
int Q = in();
rep(i, Q) {
int A = in() - 1, B = in() - 1, C = in() - 1;
int X = bicc.belongs[A], Y = bicc.belongs[B], Z = bicc.belongs[C];
if (lca.dist(X, Z) == lca.dist(X, Y) + lca.dist(Y, Z)) {
puts("OK");
} else {
puts("NG");
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment