From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 graph/LCA.cpp | 24 ++++++++++++++++++++++++
 1 file changed, 24 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..bdb8f12
--- /dev/null
+++ b/graph/LCA.cpp
@@ -0,0 +1,24 @@
+vector<vector<int>> adjlist();
+vector<int> visited();
+vector<int> first();
+vector<int> depth();
+
+void initLCA(int gi, int d, int& c) {
+	visited[c] = gi, depth[c] = d, first[gi] = min(c, first[gi]), c++;
+	for(int gn : adjlist[gi]) {
+		initLCA(gn, d+1, c);
+		visited[c] = gi, depth[c] = d, c++;
+}}
+
+int getLCA(int a, int b) {
+	return visited[query(min(first[a], first[b]), max(first[a], first[b]))];
+}
+
+void exampleUse() {
+	int c = 0;
+	visited = vector<int>(2*adjlist.size());
+	first = vector<int>(adjlist.size(), 2*adjlist.size());
+	depth = vector<int>(2*adjlist.size());
+	initLCA(0, 0, c);
+	init(depth);
+}
-- 
cgit v1.2.3