From 1d938c77d5235ac9b04095114d316b8bef7ac8a3 Mon Sep 17 00:00:00 2001
From: JBatzill <batzilljohannes@gmail.com>
Date: Sat, 22 Nov 2014 20:10:54 +0100
Subject: Added LCA, tested on icpc prob.

---
 graph/LCA.cpp | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
 create mode 100644 graph/LCA.cpp

(limited to 'graph/LCA.cpp')

diff --git a/graph/LCA.cpp b/graph/LCA.cpp
new file mode 100644
index 0000000..d252bac
--- /dev/null
+++ b/graph/LCA.cpp
@@ -0,0 +1,16 @@
+//RMQ muss hinzugefügt werden!
+vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
+vector<vector<int>> graph(MAX_N);
+
+void initLCA(int gi, int d, int &c) {
+	visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
+	for(int gn : graph[gi]) {
+		initLCA(gn, d+1, c);
+		visited[c] = gi, depth[c] = d, c++;
+	}
+}
+//[a, b]
+int getLCA(int a, int b) {
+	return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))];
+}
+//=> int c = 0; initLCA(0,0,c); initRMQ(); done!
-- 
cgit v1.2.3