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, = map(len, G)
    while stk:
        v = stk[-1]
        if anc[v] == -1:
            anc[v] = v
        else:
            anc[unite(v, G[v][it[v]])] = v

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

Verified

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

参考

戻る