From fa3508ac4b96b39435ab8671412126fefc59bea8 Mon Sep 17 00:00:00 2001
From: JBatzill <batzilljohannes@gmail.com>
Date: Thu, 3 Dec 2015 01:07:53 +0100
Subject: added runtime of lca

initLCA is dfs on a tree => O(n)
---
 graph/LCA.cpp | 2 ++
 1 file changed, 2 insertions(+)

(limited to 'graph')

diff --git a/graph/LCA.cpp b/graph/LCA.cpp
index b4e6bdd..da3b5f7 100644
--- a/graph/LCA.cpp
+++ b/graph/LCA.cpp
@@ -2,6 +2,7 @@
 vector<int> visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N);
 vector<vector<int>> graph(MAX_N);
 
+//Runtime: O(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]) {
@@ -10,6 +11,7 @@ void initLCA(int gi, int d, int &c) {
 	}
 }
 //[a, b]
+//Runtime: O(1)
 int getLCA(int a, int b) {
 	return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))];
 }
-- 
cgit v1.2.3