-
Notifications
You must be signed in to change notification settings - Fork 1.5k
/
LCA.h
38 lines (34 loc) · 1.05 KB
/
LCA.h
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
/*******************************************************************************
*
*
* /\ | _ _ ._ o _|_ |_ ._ _ _
* /--\ | (_| (_) | | |_ | | | | | _>
* _|
*
* LCA Finding using Binary Lifting and Dynamic Programming
*
* Features:
* 1. Answers Query about LCA of two nodes in O(log N)
* where N is the total number of nodes in a tree.
*
* https://en.wikipedia.org/wiki/Lowest_common_ancestor
* http://www.csegeek.com/csegeek/view/tutorials/algorithms/trees/tree_part12.php
******************************************************************************/
#ifndef LCA_H
#define LCA_H
#include <vector>
class LCA
{
public:
LCA(std::vector< std::pair<int,int> > edges);
int lcaQuery(int a, int b);
private:
int getMaxLog();
void initDP();
void dfs(int currentNode, int currentParent);
std::vector< std::vector<int> > adjList, binaryLiftDp;
std::vector<int> parent, nodeHeight;
std::vector<bool> visited;
int _numberOfNodes, _maxLog;
};
#endif // LCA_H