Lowest Common Ancestor (Tarjan’s off-line algorithm)

概要

根付き木\(T\)のある頂点\(u, v\)について、共通の祖先であり、根頂点から最も遠い位置にあるLCAの頂点を求める。

オフライン処理では深さ優先探索を行いながら各クエリ \((u, v)\) のLCAを求める。

探索中は、現在の頂点\(v\)と根頂点間のパス上の各頂点\(w\)について、(DFSで既に訪れた頂点の中から)頂点\(w\)が頂点\(v\)とのLCAとなる頂点\(u\)の集合を素集合データ構造で管理する。

そして、各頂点\(v\)ごとに答える必要のあるクエリ \((u, v)\) に対し LCA \(w\) を素集合データ構造から求める。

実装

計算量は 頂点数 \(N\) , クエリ数 \(Q\) に対し \(O(N \alpha(N) + Q)\) (\(\alpha\)はアッカーマン関数の逆関数)

# G is a tree
def lca(N, G, s, QS):
    res = [-1]*len(QS)

    A = [[] for i in range(N)]
    for i, (u, v) in enumerate(QS):
        if u == v:
            res[i] = u
            continue
        A[u].append((v, i))
        A[v].append((u, i))

    # disjoint data structure
    *prt, = range(N)
    def root(x):
        if x == prt[x]:
            return x
        prt[x] = x = root(prt[x])
        return x
    def unite(x, y):
        px = root(x); py = root(y)
        if px < py:
            prt[py] = px
            return px
        else:
            prt[px] = py
            return py

    anc = [-1]*N
    # DFS (non-recursive)
    stk = [s]
    it = [0]*N
    while stk:
        v = stk[-1]
        if it[v] == 0:
            anc[v] = v
        else:
            anc[unite(v, G[v][it[v]-1])] = v

        if it[v] < len(G[v]):
            stk.append(G[v][it[v]])
            it[v] += 1
        else:
            pv = root(v)
            for w, i in A[v]:
                if anc[w] != -1 and pv != root(w):
                    res[i] = anc[root(w)]
            stk.pop()
    return res

Verified

  • AOJ: "GRL_5_C: Tree - Lowest Common Ancestor": source (Python3, 0.94sec)

参考