AtCoder ARC039 D - 旅行会社高橋君

atcoder.jp

概要

\(N\)頂点\(M\)辺の単純な無向グラフがあります。以下のクエリが\(Q\)個与えられるので答えてください。

• 頂点\(A, B, C\)について、同じ辺を2度通らないパス\(A\)→\(B\)→\(C\)は存在するか

制約：\(3 \le N \le 10 ^ 5\)、\(1 \le M \le 2 \times 10 ^ 5\)、\(1 \le Q \le 10 ^ 5\)

考察

頂点\(v\)が属する二重辺連結成分分解後の頂点を\(group(v)\)と表記します。

\(group(v) = group(u)\)を満たす頂点\(v, u\)の間には、必ず辺を共有しないパス（辺素パス）が存在します。これは、最大フロー最小カット定理により、フローを2流せる場合は、辺を2本カットしないと連結成分が分解されないことから言えます。

したがって、\(group(A) = group(B)\)のとき、頂点\(A\)から頂点\(B\)に行く際に通るパス上の辺を使うことなく頂点\(C\)に行くことができます。同様に、\(group(B) = group(C)\)のときも可能です。逆に\(group(A) = group(C) \land group(A) \ne group(B)\)のときは、必ず同じ橋を2度使うことになります。

あと残っているのは、すべての頂点が異なる二重辺連結成分に属する場合です。これは、二重辺連結成分分解後の木について、頂点\(A\)と頂点\(C\)の最短経路上に頂点\(B\)があれば可能、なければ不可能です。これは、少しでも迂回すると同じ辺を2度使ってしまうことから言えます。

実装

LowLinkを使って橋を列挙したあと、二重辺連結成分分解をします。こうしてできあがった木の最短経路を素早く求めるためにLCAを使います。

計算量は、橋の列挙が\(O(M)\)、二重辺連結成分分解が\(O(M \log M)\)、LCAの構築に\(O(N \log N)\)、クエリ毎に最短経路を求めるのに\(O(Q \log N)\)で、合計\(O(M \log M + (N + Q) \log N)\)です。

#include <bits/stdc++.h>
using namespace std;

struct UnWeightedGraph {
  struct Edge {
    int to;
    Edge(int to) : to(to) {}
  };
  vector<vector<Edge>> edges;
  int n;
  UnWeightedGraph(int n) : n(n) {
    edges.assign(n, vector<Edge>());
  }
  void add_edge(int v, int u) {
    edges[v].emplace_back(u);
  }
  vector<Edge> &operator[](int x) {
    return edges[x];
  }
};

template <typename Graph>
struct LowLink {
  using A = vector<int>;
  using B = vector<pair<int, int>>;
  Graph &g;
  int n;
  vector<bool> seen;
  vector<int> ord, low;
  A articulation;
  B bridge;
  LowLink(Graph &g) : g(g), n(g.n) {}
  void dfs(int v, int p, int &k) {
    seen[v] = true;
    ord[v] = k++;
    low[v] = ord[v];
    bool is = false;
    int cnt = 0;
    for (auto e : g[v]) {
      int u = e.to;
      if (seen[u])  {
        if (u != p) low[v] = min(low[v], ord[u]);
        continue;
      }
      cnt++;
      dfs(u, v, k);
      low[v] = min(low[v], low[u]);
      if (p != -1 && ord[v] <= low[u]) is = true;
      if (ord[v] < low[u]) bridge.emplace_back(minmax(v, u));
    }
    if (p == -1 && cnt > 1) is = true;
    if (is) articulation.push_back(v);
  }
  pair<A, B> build() {
    seen.assign(n, false);
    ord.assign(n, 0);
    low.assign(n, 0);
    articulation.clear();
    bridge.clear();
    int k = 0;
    dfs(0, -1, k);
    return pair<A, B>(articulation, bridge);
  }
  pair<A, B> operator()() {
    return build();
  }
};

template <typename Graph>
struct TwoEdgeConnectedComponent {
  using B = vector<pair<int, int>>;
  Graph &g;
  int n;
  vector<bool> seen;
  vector<int> group;
  set<pair<int, int>> b;
  TwoEdgeConnectedComponent(Graph &g) : g(g), n(g.n), group(n) {}
  void dfs(int v, int p, int k) {
    seen[v] = true;
    group[v] = k;
    for (auto e : g[v]) {
      int u = e.to;
      if (u == p) continue;
      if (seen[u]) continue;
      if (b.find(minmax(v, u)) != b.end()) continue;
      dfs(u, v, k);
    }
  }
  vector<int> decompose(B bridge) {
    seen.assign(n, false);
    b.clear();
    b.insert(bridge.begin(), bridge.end());
    int k = 0;
    for (int i = 0; i < n; i++) {
      if (seen[i]) continue;
      dfs(i, -1, k++);
    }
    return group;
  }
  vector<int> operator()(B bridge) {
    return decompose(bridge);
  }
};

template <typename Graph>
struct LowestCommonAncestor {
  Graph &g;
  int n;
  int l;
  vector<vector<int>> par;
  vector<int> dep;
  LowestCommonAncestor(Graph &g) : g(g), n(g.n), dep(n) {
    l = 0;
    while ((1 << l) < n) l++;
    par.assign(n + 1, vector<int>(l, n));
  }
  void dfs(int v = 0, int d = 0, int p = -1) {
    if (p != -1) par[v][0] = p;
    dep[v] = d;
    for (auto e : g[v]) {
      if (e.to == p) continue;
      dfs(e.to, d + 1, v);
    }
  }
  void build() {
    dfs();
    for (int i = 0; i < l - 1; i++) {
      for (int v = 0; v < n; v++) {
        par[v][i + 1] = par[par[v][i]][i];
      }
    }
  }
  int lca(int v, int u) {
    if (dep[v] < dep[u]) swap(v, u);
    int gap = dep[v] - dep[u];
    for (int i = l - 1; i >= 0; i--) {
      if ((1 << i) & gap) v = par[v][i];
    }
    if (v == u) return v;
    for (int i = l - 1; i >= 0; i--) {
      int pv = par[v][i];
      int pu = par[u][i];
      if (pv != pu) v = pv, u = pu;
    }
    return par[v][0];
  }
  int dist(int v, int u) {
    int a = lca(v, u);
    return dep[v] + dep[u] - dep[a] * 2;
  }
};

int main() {
  int N, M; cin >> N >> M;
  auto g = UnWeightedGraph(N);
  auto low = LowLink<UnWeightedGraph>(g);
  auto tec = TwoEdgeConnectedComponent<UnWeightedGraph>(g);
  for (int i = 0; i < M; i++) {
    int v, u; cin >> v >> u;
    v--, u--;
    g.add_edge(v, u);
    g.add_edge(u, v);
  }
  auto bridge = low().second;
  auto t = tec(bridge);

  int L = *max_element(t.begin(), t.end()) + 1;

  auto h = UnWeightedGraph(L);
  auto lca = LowestCommonAncestor<UnWeightedGraph>(h);
  for (int v = 0; v < N; v++) {
    for (auto e : g[v]) {
      int u = e.to;
      if (t[v] == t[u]) continue;
      h.add_edge(t[v], t[u]);
    }
  }
  lca.build();
  int Q; cin >> Q;
  while (Q--) {
    int a, b, c; cin >> a >> b >> c;
    a--, b--, c--;
    if (t[a] == t[b] || t[b] == t[c]) {
      cout << "OK" << '\n';
      continue;
    }
    if (t[a] == t[c]) {
      cout << "NG" << '\n';
      continue;
    }
    if (lca.dist(t[a], t[c]) == lca.dist(t[a], t[b]) + lca.dist(t[b], t[c])) {
      cout << "OK" << '\n';
    } else {
      cout << "NG" << '\n';
    }
  }
  return 0;
}

感想

実装は一見重そう（200行）ですが、ほとんどの部分がライブラリ化可能なので、実際はそれほど重くないかもしれません。