lca

ソースコード

 1#include <vector>
 2#include <cassert>
 3#include <stack>
 4#include <climits>
 5#include "titan_cpplib/data_structures/sparse_table.cpp"
 6using namespace std;
 7
 8// LCA
 9namespace titan23 {
10
11    /**
12     * @brief 静的なグラフに対しLCAを求めるだけのライブラリ
13     * <O(nlogn), O(1)>
14     */
15    class LCA {
16      private:
17        static int __LCA_op(int s, int t) { return min(s, t); }
18        static int __LCA_e() { return INT_MAX; }
19        int n;
20        vector<int> path, nodein, par;
21        SparseTable<int, __LCA_op, __LCA_e> st;
22
23      public:
24        LCA() {}
25
26        //! 隣接リスト `G` 、根 `root` として前計算をする / `O(nlogn)`
27        LCA(const vector<vector<int>> &G, const int root) :
28                n((int)G.size()), path(n), nodein(n, -1), par(n, -1) {
29            int time = -1, ptr = 0;
30            int s[n];
31            s[ptr++] = root;
32            while (ptr) {
33                int v = s[--ptr];
34                if (time >= 0) {
35                    path[time] = par[v];
36                }
37                ++time;
38                nodein[v] = time;
39                for (const int &x: G[v]) {
40                    if (nodein[x] != -1) continue;
41                    par[x] = v;
42                    s[ptr++] = x;
43                }
44            }
45            vector<int> a(n);
46            for (int i = 0; i < n; ++i) {
47                a[i] = nodein[path[i]];
48            }
49            st = SparseTable<int, __LCA_op, __LCA_e>(a);
50        }
51
52        //! `u`, `v` の lca を求める / `O(1)`
53        int lca(const int u, const int v) const {
54            if (u == v) return u;
55            int l = nodein[u], r = nodein[v];
56            if (l > r) swap(l, r);
57            return path[st.prod(l, r)];
58        }
59
60        //! 頂点集合 `a` の lca を求める / `O(|a|)`
61        int lca_mul(const vector<int> &a) const {
62            assert(!a.empty());
63            int l = n*2+1;
64            int r = -l;
65            for (const int &e: a) {
66                int x = nodein[e];
67                if (l > x) l = x;
68                if (r < x) r = x;
69            }
70            if (l == r) return a[0];
71            return path[st.prod(l, r)];
72        }
73    };
74}  // namspace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/lca.cpp