-
Notifications
You must be signed in to change notification settings - Fork 0
/
LCA.cpp
102 lines (81 loc) · 1.95 KB
/
LCA.cpp
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
//----------------Lowest Common Ancestor-----------------------
*********** Don't Forget to create Sparse Table at ending***********
cal_sparse_table(1,0);
//1) Binary Lifting
const int N=100005,M=22;
vector<int> gr[N];
int Par[N][M],dep[N];
// O(nlogn) Tree for root node 1 with par 0;
void cal_sparse_table(int cur,int par)
{
Par[cur][0]=par; // Base case
// Filling All 2^j distance parrent of cur in logN
for(int j=1;j<M;j++)
Par[cur][j]=Par[Par[cur][j-1]][j-1];
for(auto child:gr[cur])
if(child!=par)
{
dep[child]=dep[cur]+1;
cal_sparse_table(child,cur);
}
return;
}
//O(logN)
int LCA_using_BL(int u,int v)
{
if(u==v)return u;
// dep[u]>dep[v]
if(dep[u]<dep[v])swap(u,v);
int diff=dep[u]-dep[v];
for(int i=M-1;~i;i--)
if((diff>>i)&1)
{
u=Par[u][i];
}
// Now Both u and v are on Same Level
if(u==v)return u; // Case if u is ancestor of v;
for(int i=M-1;~i;i--)
if(Par[u][i]!=Par[v][i])
{
u=Par[u][i];
v=Par[v][i];
}
// Now I'm Standing on Different Nodes;
return Par[u][0];
}
//2) Eulor Tour 3- TimeIn And TimeOut
const int N=100005,M=22;
vector<int> gr[N];
int Par[N][M],dep[N],tin[N],tout[N],tim=0;
// O(nlogn)
void cal_sparse_table(int cur,int par)
{
tin[cur]= ++tim;
Par[cur][0]=par; // Base case
// Filling All 2^j distance parrent of cur in logN
for(int j=1;j<M;j++)
Par[cur][j]=Par[Par[cur][j-1]][j-1];
for(auto child:gr[cur])
if(child!=par)
{
cal_sparse_table(child,cur);
}
tout[cur]=tim;
return;
}
bool is_ancestor(int u,int v)
{
return (tin[u]<=tin[v] and tout[u]>=tout[v]);
}
//O(logN)
int LCA_using_timer(int u,int v)
{
if(is_ancestor(u,v))return u;
if(is_ancestor(v,u))return v;
// Now Lift u upper;
for(int i=M-1;~i;i--)
if(!is_ancestor(Par[u][i],v))
u=Par[u][i];
return Par[u][0];
}
tin[0]=0; tout[0]=N+1;