Source code for titan_pylib.graph.lca

 1from titan_pylib.data_structures.sparse_table.sparse_table_RmQ import SparseTableRmQ
 2
 3

[docs]
 4class LCA:
 5    """LCA を定数倍良く求めます。
 6
 7    :math:`< O(NlogN), O(1) >`
 8    https://github.com/cheran-senthil/PyRival/blob/master/pyrival/graphs/lca.py
 9    """
10
11    def __init__(self, G: list[list[int]], root: int) -> None:
12        """根が ``root`` の重み無し隣接リスト ``G`` で表されるグラフに対して LCA を求めます。
13        時間・空間 :math:`O(n\\log{n})` です。
14
15        Args:
16          G (list[list[int]]): 隣接リストです。
17          root (int): 根です。
18        """
19        _n = len(G)
20        path = [-1] * _n
21        nodein = [-1] * _n
22        par = [-1] * _n
23        curtime = -1
24        stack = [root]
25        while stack:
26            v = stack.pop()
27            path[curtime] = par[v]
28            curtime += 1
29            nodein[v] = curtime
30            for x in G[v]:
31                if nodein[x] != -1:
32                    continue
33                par[x] = v
34                stack.append(x)
35        self._n = _n
36        self._path = path
37        self._nodein = nodein
38        self._st: SparseTableRmQ[int] = SparseTableRmQ((nodein[v] for v in path), e=_n)
39

[docs]
40    def lca(self, u: int, v: int) -> int:
41        """頂点 ``u`` と頂点 ``v`` の LCA を返します。
42        :math:`O(1)` です。
43        """
44        if u == v:
45            return u
46        l, r = self._nodein[u], self._nodein[v]
47        if l > r:
48            l, r = r, l
49        return self._path[self._st.prod(l, r)]

50

[docs]
51    def lca_mul(self, a: list[int]) -> int:
52        """頂点集合 ``a`` の LCA を返します。"""
53        if all(a[i] == a[i + 1] for i in range(len(a) - 1)):
54            return a[0]
55        l = self._n + 1
56        r = -l
57        for e in a:
58            e = self._nodein[e]
59            if l > e:
60                l = e
61            if r < e:
62                r = e
63        return self._path[self._st.prod(l, r)]