Adding new code for sparse table implementation and LCA.

1 files changed, 28 insertions, 0 deletions

diff --git a/graph/lca.cpp b/graph/lca.cpp
new file mode 100644
index 0000000..d6548e9
--- /dev/null
+++ b/graph/lca.cpp
@@ -0,0 +1,28 @@
+struct LCA {
+  vector<int> depth, visited, first;
+  int idx;
+  SparseTable st;
+
+  void init(vector<vector<int>> &g, int root) { // Laufzeit: O(|V|)
+    depth.assign(2 * g.size(), 0);
+    visited.assign(2 * g.size(), -1);
+    first.assign(g.size(), 2 * g.size());
+    idx = 0;
+    visit(g, root, 0);
+    st.init(&depth);
+  }
+
+  void visit(vector<vector<int>> &g, int v, int d) {
+    visited[idx] = v, depth[idx] = d, first[v] = min(idx, first[v]), idx++;
+
+    for (int w : g[v]) {
+      if (first[w] == 2 * (int)g.size()) {
+        visit(g, w, d + 1);
+        visited[idx] = v, depth[idx] = d, idx++;
+  }}}
+
+  int getLCA(int a, int b) { // Laufzeit: O(1)
+    if (first[a] > first[b]) swap(a, b);
+    return visited[st.queryIdempotent(first[a], first[b])];
+  }
+};