forked from xtaci/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlca_demo.cpp
More file actions
117 lines (111 loc) · 3.5 KB
/
Copy pathlca_demo.cpp
File metadata and controls
117 lines (111 loc) · 3.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include "LCA.h"
#include <cstdio>
#include <vector>
#include <iostream>
/**
*Constructor is initialized with a Adjacency List that
*describe a tree and If It doesn't describe a tree it asserts failure.
*/
LCA::LCA(std::vector< std::pair<int,int> > edges): _numberOfNodes(edges.size() + 1), _maxLog(getMaxLog())
{
//First we initialize the needed vectors
parent.resize(_numberOfNodes);
nodeHeight.resize(_numberOfNodes);
visited.resize(_numberOfNodes);
adjList.resize(_numberOfNodes);
binaryLiftDp = std::vector< std::vector<int> >(_numberOfNodes, std::vector<int>(_maxLog));
/**Construction of the Adjacency List to increase
*The efficiency of the tree traversal to O(V + E).
*/
for(auto edge : edges){
adjList[edge.first].push_back(edge.second);
adjList[edge.second].push_back(edge.first);
}
//Initialize the Dynamic programming Vector.
initDP();
}
/**
*DFS is used to find the parent and the height of each node
*allowing the use of Binary Lifting.
*/
void LCA::dfs(int currentNode, int currentParent)
{
visited[currentNode] = true;
parent[currentNode] = currentParent;
nodeHeight[currentNode] = nodeHeight[currentParent] + 1;
int adjacencySize = adjList[currentNode].size();
for(int idx = 0; idx < adjacencySize; idx++){
int nextNode = adjList[currentNode][idx];
if(!visited[nextNode])
{
dfs(nextNode, currentNode);
}
}
}
/**
*Used to Calculate the Log to the base of two
*for the number of the nodes to create the sparse table
*used in binary Lifting.
*/
int LCA::getMaxLog(){
int curValue = 1;
int curLog = 1;
while(curValue < _numberOfNodes) curValue *= 2, curLog++;
return curLog;
}
void LCA::initDP()
{
dfs(0, -1);
for(int i = 0; i < _numberOfNodes; i++) binaryLiftDp[i][0] = parent[i];
for(int i = 1; i <= _maxLog; i++)
{
for(int j = 0; j < _numberOfNodes; j++)
{
/**
* Since the ith parent of the current node is equal to
* the ith / 2 parent to the ith /2 parent of the current node
* That's why the Recurrence relation is described as follow
*/
if(binaryLiftDp[j][i - 1] != -1)
binaryLiftDp[j][i] = binaryLiftDp[binaryLiftDp[j][i - 1]][i - 1];
else binaryLiftDp[j][i] = -1;
}
}
}
int LCA::lcaQuery(int a, int b)
{
/**
* First Both nodes must have same height
* So we will rise the node with the deeper height up in
* the tree to where they're equal.
*/
if(nodeHeight[a] < nodeHeight[b]) std::swap(a,b);
for(int i = _maxLog; i >= 0; i--)
{
if(binaryLiftDp[a][i] + 1 && nodeHeight[binaryLiftDp[a][i]] >= nodeHeight[b])
a = binaryLiftDp[a][i];
}
/**
* If the node Lower is the LCA then return it.
* Else keep moving both nodes up as much as they aren't the same
* until it's only 1 node left which is the direct parent of both of them
*/
if(a == b) return a;
for(int i = _maxLog; i >= 0; i--)
{
if(binaryLiftDp[a][i] + 1 && binaryLiftDp[a][i] - binaryLiftDp[b][i])
a = binaryLiftDp[a][i], b = binaryLiftDp[b][i];
}
return parent[a];
}
int main(){
std::vector< std::pair<int,int> > edges;
edges.push_back({0,1});
edges.push_back({1,2});
edges.push_back({2,3});
edges.push_back({1,4});
LCA* l = new LCA(v);
std::cout << l->lcaQuery(0,1) << endl;
std::cout << l->lcaQuery(3,4) << endl;
std::cout << l->lcaQuery(3,2) << endl;
}