Spaghetti Source logo

オフライン最小共通先祖 (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

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.10.27 06:57:26.