mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 15:39:42 +08:00
b88128dd97
* algorithm: LCA by binary lifting * removed trailing spaces * reduced code duplication by importing code from other file * made requested changes
81 lines
1.3 KiB
JavaScript
81 lines
1.3 KiB
JavaScript
import lcaBinaryLifting from '../LCABinaryLifting'
|
|
|
|
// The graph for Test Case 1 looks like this:
|
|
//
|
|
// 0
|
|
// /|\
|
|
// / | \
|
|
// 1 3 5
|
|
// / \ \
|
|
// 2 4 6
|
|
// \
|
|
// 7
|
|
// / \
|
|
// 11 8
|
|
// \
|
|
// 9
|
|
// \
|
|
// 10
|
|
|
|
test('Test case 1', () => {
|
|
const root = 0
|
|
const graph = [
|
|
[0, 1],
|
|
[0, 3],
|
|
[0, 5],
|
|
[5, 6],
|
|
[1, 2],
|
|
[1, 4],
|
|
[4, 7],
|
|
[7, 11],
|
|
[7, 8],
|
|
[8, 9],
|
|
[9, 10]
|
|
]
|
|
const queries = [
|
|
[1, 3],
|
|
[6, 5],
|
|
[3, 6],
|
|
[7, 10],
|
|
[8, 10],
|
|
[11, 2],
|
|
[11, 10]
|
|
]
|
|
const lowestCommonAncestors = lcaBinaryLifting(root, graph, queries)
|
|
expect(lowestCommonAncestors).toEqual([0, 5, 0, 7, 8, 1, 7])
|
|
})
|
|
|
|
// The graph for Test Case 2 looks like this:
|
|
//
|
|
// 0
|
|
// / \
|
|
// 1 2
|
|
// / \ \
|
|
// 3 4 5
|
|
// / / \
|
|
// 6 7 8
|
|
|
|
test('Test case 2', () => {
|
|
const root = 0
|
|
const graph = [
|
|
[0, 1],
|
|
[0, 2],
|
|
[1, 3],
|
|
[1, 4],
|
|
[2, 5],
|
|
[3, 6],
|
|
[5, 7],
|
|
[5, 8]
|
|
]
|
|
const queries = [
|
|
[1, 2],
|
|
[3, 4],
|
|
[5, 4],
|
|
[6, 7],
|
|
[6, 8],
|
|
[7, 8]
|
|
]
|
|
const lowestCommonAncestors = lcaBinaryLifting(root, graph, queries)
|
|
expect(lowestCommonAncestors).toEqual([0, 1, 0, 0, 0, 5])
|
|
})
|