オフライン最小共通先祖 (Tarjan)

説明

根 r が指定された無向木 T を考える．頂点 u, v \in T に対し，u と v の両方の先祖であって，もっとも深いもの（もっとも u, v に近いもの）を u と v の最小共通先祖という．ここではオフライン最小共通先祖問題，すなわち，頂点の組たち { (u_i, v_i) } が与えられたとき，すべての組に対してそれぞれ最小共通先祖を求める問題を考える．

この問題について，Tarjan によって Union-Find と深さ優先探索を組み合わせたアルゴリズムが知られている．

計算量

O(E A(V))，ただし A はアッカーマン関数の逆関数．

使い方

const Graph &g

無向木をあらわすグラフ，すなわち (u,v) \in g[u] ならば (v,u) \in g[v] であり，任意の二頂点間に一意パスが存在するもの．

int r

木の頂点 r

vector<Query> &qs

最小共通先祖のクエリのリスト．query.u, query.v が最小共通先祖を求めたい二頂点．実行後，副作用で query.w に最小共通先祖の値が入る．

ソースコード

struct Query {
  int u, v, w;
  Query(int u, int v) : u(u), v(v), w(-1) { }
};
void visit(const Graph &g, int u, int w,
    vector<Query> &qs, vector<int> &color,
    vector<int> &ancestor, UnionFind &uf) {
  ancestor[ uf.root(u) ] = u;
  FOR(e, g[u]) if (e->dst != w) {
    visit(g, e->dst, u, qs, color, ancestor, uf);
    uf.unionSet( e->src, e->dst );
    ancestor[ uf.root(u) ] = u;
  }
  color[u] = 1;
  FOR(q, qs) {
    int w = (q->v == u ? q->u : q->u == u ? q->v : -1);
    if (w >= 0 && color[w]) q->w = ancestor[ uf.root(w) ];
  }
}
void leastCommonAncestor(const Graph &g, int r, vector<Query> &qs) {
  UnionFind uf(g.size());
  vector<int> color(g.size()), ancestor(g.size());
  visit(g, r, -1, qs, color, ancestor, uf);
}

Verified

• UVA 10938 (Flea circus), 2.229 MS, 1.712 KB