From 9facd3655e2b86799699a6fdbd566cb4b2a7fb1c Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Fri, 22 Dec 2017 12:49:35 +0100 Subject: Adding new code for sparse table implementation and LCA. --- graph/LCA.cpp | 21 --------------------- 1 file changed, 21 deletions(-) delete mode 100644 graph/LCA.cpp (limited to 'graph/LCA.cpp') diff --git a/graph/LCA.cpp b/graph/LCA.cpp deleted file mode 100644 index c79cc5c..0000000 --- a/graph/LCA.cpp +++ /dev/null @@ -1,21 +0,0 @@ -vector visited(2*MAX_N), first(MAX_N, 2*MAX_N), depth(2*MAX_N); -vector> graph(MAX_N); - -// Funktioniert nur mit von der Wurzel weggerichteten Kanten. -// Falls ungerichtete Kanten, visited-check einführen. -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++; -}} - -int getLCA(int a, int b) { // Laufzeit: O(1) - return visited[queryRMQ( - min(first[a], first[b]), max(first[a], first[b]))]; -} - -// Benutzung: -int c = 0; -initLCA(0, 0, c); -initRMQ(); // Ersetze das data im RMQ-Code von oben durch depth. -- cgit v1.2.3