From abdde03e94626f0994498fd746b2afe4364acb2a Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Thu, 6 Oct 2016 22:15:15 +0200 Subject: Adapt LCA code. --- graph/LCA.cpp | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) (limited to 'graph/LCA.cpp') diff --git a/graph/LCA.cpp b/graph/LCA.cpp index 67a4f3b..f494b0b 100644 --- a/graph/LCA.cpp +++ b/graph/LCA.cpp @@ -1,18 +1,19 @@ -//RMQ muss hinzugefuegt werden! vector visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); vector> graph(MAX_N); -//Runtime: O(n) -void initLCA(int gi, int d, int &c) { +void initLCA(int gi, int d, int &c) { // Laufzeit: O(n) 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] -//Runtime: O(1) -int getLCA(int a, int b) { - return visited[queryRMQ(min(first[a], first[b]), max(first[a], first[b]))]; +}} + +int getLCA(int a, int b) { // Laufzeit: O(1) + return visited[queryRMQ( + min(first[a], first[b]), max(first[a], first[b]))]; } -//=> int c = 0; initLCA(0,0,c); initRMQ(); done! [rmq on depth] + +// Benutzung: +int c = 0; +initLCA(0, 0, c); +initRMQ(); // Ersetze das data im RMQ-Code von oben durch depth. -- cgit v1.2.3