Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb88128d

Browse files
authored
algorithm: LCA by binary lifting (#1237)
* algorithm: LCA by binary lifting* removed trailing spaces* reduced code duplication by importing code from other file* made requested changes
1 parent0fab492 commitb88128d

File tree

3 files changed

+142
-1
lines changed

3 files changed

+142
-1
lines changed

‎Graphs/BinaryLifting.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
* Tutorial on Binary Lifting: https://codeforces.com/blog/entry/100826
1010
*/
1111

12-
classBinaryLifting{
12+
exportclassBinaryLifting{
1313
constructor(root,tree){
1414
this.root=root
1515
this.connections=newMap()

‎Graphs/LCABinaryLifting.js

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
/**
2+
* Author: Adrito Mukherjee
3+
* Findind Lowest Common Ancestor By Binary Lifting implementation in JavaScript
4+
* The technique requires preprocessing the tree in O(N log N) using dynamic programming)
5+
* It can be used to find Lowest Common Ancestor of two nodes in O(log N)
6+
* Tutorial on Lowest Common Ancestor: https://www.geeksforgeeks.org/lca-in-a-tree-using-binary-lifting-technique
7+
*/
8+
9+
import{BinaryLifting}from'./BinaryLifting'
10+
11+
classLCABinaryLiftingextendsBinaryLifting{
12+
constructor(root,tree){
13+
super(root,tree)
14+
this.depth=newMap()// depth[node] stores the depth of node from root
15+
this.depth.set(root,1)
16+
this.dfsDepth(root,root)
17+
}
18+
19+
dfsDepth(node,parent){
20+
// DFS to find depth of every node in the tree
21+
for(constchildofthis.connections.get(node)){
22+
if(child!==parent){
23+
this.depth.set(child,this.depth.get(node)+1)
24+
this.dfsDepth(child,node)
25+
}
26+
}
27+
}
28+
29+
getLCA(node1,node2){
30+
// We make sure that node1 is the deeper node among node1 and node2
31+
if(this.depth.get(node1)<this.depth.get(node2)){
32+
[node1,node2]=[node2,node1]
33+
}
34+
// We check if node1 is the ancestor of node2, and if so, then return node1
35+
constk=this.depth.get(node1)-this.depth.get(node2)
36+
node1=this.kthAncestor(node1,k)
37+
if(node1===node2){
38+
returnnode1
39+
}
40+
41+
for(leti=this.log-1;i>=0;i--){
42+
if(this.up.get(node1).get(i)!==this.up.get(node2).get(i)){
43+
node1=this.up.get(node1).get(i)
44+
node2=this.up.get(node2).get(i)
45+
}
46+
}
47+
returnthis.up.get(node1).get(0)
48+
}
49+
}
50+
51+
functionlcaBinaryLifting(root,tree,queries){
52+
constgraphObject=newLCABinaryLifting(root,tree)
53+
constlowestCommonAncestors=[]
54+
for(const[node1,node2]ofqueries){
55+
constlca=graphObject.getLCA(node1,node2)
56+
lowestCommonAncestors.push(lca)
57+
}
58+
returnlowestCommonAncestors
59+
}
60+
61+
exportdefaultlcaBinaryLifting

‎Graphs/test/LCABinaryLifting.test.js

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
importlcaBinaryLiftingfrom'../LCABinaryLifting'
2+
3+
// The graph for Test Case 1 looks like this:
4+
//
5+
// 0
6+
// /|\
7+
// / | \
8+
// 1 3 5
9+
// / \ \
10+
// 2 4 6
11+
// \
12+
// 7
13+
// / \
14+
// 11 8
15+
// \
16+
// 9
17+
// \
18+
// 10
19+
20+
test('Test case 1',()=>{
21+
constroot=0
22+
constgraph=[
23+
[0,1],
24+
[0,3],
25+
[0,5],
26+
[5,6],
27+
[1,2],
28+
[1,4],
29+
[4,7],
30+
[7,11],
31+
[7,8],
32+
[8,9],
33+
[9,10]
34+
]
35+
constqueries=[
36+
[1,3],
37+
[6,5],
38+
[3,6],
39+
[7,10],
40+
[8,10],
41+
[11,2],
42+
[11,10]
43+
]
44+
constlowestCommonAncestors=lcaBinaryLifting(root,graph,queries)
45+
expect(lowestCommonAncestors).toEqual([0,5,0,7,8,1,7])
46+
})
47+
48+
// The graph for Test Case 2 looks like this:
49+
//
50+
// 0
51+
// / \
52+
// 1 2
53+
// / \ \
54+
// 3 4 5
55+
// / / \
56+
// 6 7 8
57+
58+
test('Test case 2',()=>{
59+
constroot=0
60+
constgraph=[
61+
[0,1],
62+
[0,2],
63+
[1,3],
64+
[1,4],
65+
[2,5],
66+
[3,6],
67+
[5,7],
68+
[5,8]
69+
]
70+
constqueries=[
71+
[1,2],
72+
[3,4],
73+
[5,4],
74+
[6,7],
75+
[6,8],
76+
[7,8]
77+
]
78+
constlowestCommonAncestors=lcaBinaryLifting(root,graph,queries)
79+
expect(lowestCommonAncestors).toEqual([0,1,0,0,0,5])
80+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp