mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 07:29:47 +08:00
d9d085faa7
* Algorithm: BinaryLifting * Update BinaryLifting.js * made the requested changes * added more comments
83 lines
1.3 KiB
JavaScript
83 lines
1.3 KiB
JavaScript
import binaryLifting from '../BinaryLifting'
|
|
|
|
// 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 = [
|
|
[2, 1],
|
|
[6, 1],
|
|
[7, 2],
|
|
[8, 2],
|
|
[10, 2],
|
|
[10, 3],
|
|
[10, 5],
|
|
[11, 3]
|
|
]
|
|
const kthAncestors = binaryLifting(root, graph, queries)
|
|
expect(kthAncestors).toEqual([1, 5, 1, 4, 8, 7, 1, 1])
|
|
})
|
|
|
|
// 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 = [
|
|
[2, 1],
|
|
[3, 1],
|
|
[3, 2],
|
|
[6, 2],
|
|
[7, 3],
|
|
[8, 2],
|
|
[8, 3]
|
|
]
|
|
const kthAncestors = binaryLifting(root, graph, queries)
|
|
expect(kthAncestors).toEqual([0, 1, 0, 1, 0, 2, 0])
|
|
})
|