ARC 039 D - 旅行会社高橋君

Problem Description:
You have a graph with N vertices, M edges. You are then given Q queries, each denoted by three indexes of nodes, A, B, and C. For every such query, you need to output whether it is possible to visit node A, B, and C, in that order, without visiting duplicate edges.

Constraints:
3 ≤ N ≤ 1e5
1 ≤ M ≤ 2e5
1 ≤ Q ≤ 1e5

Solution:
Decompose the graph with bridge-BCC, and create an induced graph by shrinking each BCC into a node. This would transform the original graph into a tree. We then know that, A, B, and C can be visited in this order iff the sum of shortest path distance of A to B, and that of B to C, is equal to that of A to C in the induced graph.

Code:

#include <bits/stdc++.h>

const int MAXN = 1 << 17;

int N, M;
std::vector<int> G[MAXN];

int imo[MAXN];
std::set<std::pair<int, int>> bridges;
std::set<int> bcc[MAXN];
int at_bcc[MAXN];
int bcc_ctr;

std::vector<int> idg[MAXN]; // induced graph
int dpt[MAXN];
int par[17][MAXN];

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    int x, y;
    std::cin >> x >> y;
    --x, --y;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }
  std::function<void(int, int, int)> mark = [&](int u, int fa, int d) {
    static int vis[MAXN];
    static int dpt[MAXN];
    vis[u] = 1;
    dpt[u] = d;
    for (int v : G[u]) {
      if (v == fa) continue;
      if (vis[v]) {
        if (dpt[v] > dpt[u]) {
          ++imo[v];
          --imo[u];
        }
      } else {
        mark(v, u, d + 1);
      }
    }
  };
  mark(0, -1, 0);
  std::function<int(int)> expand = [&](int u) {
    static int vis[MAXN];
    vis[u] = 1;
    int s = imo[u];
    for (int v : G[u]) {
      if (vis[v]) continue;
      int e = expand(v);
      if (e == 0) {
        bridges.emplace(std::make_pair(std::min(u, v), std::max(u, v)));
      }
      s += e;
    }
    return s;
  };
  expand(0);
  std::memset(at_bcc, 0xff, sizeof(at_bcc));
  for (int u = 0; u < N; ++u) {
    if (~at_bcc[u]) continue;
    std::queue<int> que;
    que.emplace(u);
    at_bcc[u] = bcc_ctr;
    bcc[bcc_ctr].emplace(u);
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      for (int w : G[v]) {
        if (~at_bcc[w] || bridges.count(std::make_pair(std::min(v, w), std::max(v, w)))) continue;
        que.emplace(w);
        at_bcc[w] = bcc_ctr;
        bcc[bcc_ctr].emplace(w);
      }
    }
    ++bcc_ctr;
  }
  for (auto it = bridges.begin(); it != bridges.end(); ++it) {
    int u = at_bcc[it->first], v = at_bcc[it->second];
    if (u == v) continue;
    idg[u].emplace_back(v);
    idg[v].emplace_back(u);
  }
  std::memset(par, 0xff, sizeof(par));
  std::function<void(int, int, int)> build_lca = [&](int u, int fa, int d) {
    dpt[u] = d;
    par[0][u] = fa;
    for (int v : idg[u]) {
      if (v == fa) continue;
      build_lca(v, u, d + 1);
    }
  };
  build_lca(0, -1, 0);
  for (int i = 0; i + 1 < 17; ++i) {
    for (int u = 0; u < N; ++u) {
      if (~par[i][u]) {
        par[i + 1][u] = par[i][par[i][u]];
      }
    }
  }
  int Q;
  std::cin >> Q;
  while (Q--) {
    int a, b, c;
    std::cin >> a >> b >> c;
    a = at_bcc[a - 1];
    b = at_bcc[b - 1];
    c = at_bcc[c - 1];
    auto lca = [&](int x, int y) {
      if (dpt[x] > dpt[y]) std::swap(x, y);
      for (int i = 16; dpt[x] < dpt[y]; --i) {
        if (dpt[y] - dpt[x] >= 1 << i) {
          y = par[i][y];
        }
      }
      if (x == y) return x;
      for (int i = 16; par[0][x] != par[0][y]; --i) {
        if (par[i][x] != par[i][y]) {
          x = par[i][x];
          y = par[i][y];
        }
      }
      return par[0][x];
    };
    auto dist = [&](int x, int y) {
      return dpt[x] + dpt[y] - 2 * dpt[lca(x, y)];
    };
    if (dist(a, c) == dist(a, b) + dist(b, c)) {
      std::cout << "OK" << std::endl;
    } else {
      std::cout << "NG" << std::endl;
    }
  }
  return 0;
}