diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/LCA.cpp | 16 |
1 files changed, 16 insertions, 0 deletions
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! |