Implementation of Binary Lifting:
C++
#include
using namespace std;
// Depth First Search
void dfs(int node, vector >& graph,
vector >& ancestor, int parent)
{
ancestor[node][0] = parent;
for (int neighbor : graph[node]) {
dfs(neighbor, graph, ancestor, node);
}
}
// Method to initialize ancestor table
void preprocess(vector >& graph,
vector >& ancestor, int V,
int maxN)
{
dfs(1, graph, ancestor, -1);
for (int j = 1; j < maxN; j++) {
for (int i = 1; i <= V; i++) {
if (ancestor[i][j - 1] != -1)
ancestor[i][j]
= ancestor[ancestor[i][j - 1]][j - 1];
}
}
}
// Method to find Kth ancestor of node
int findKthAncestor(vector >& ancestor,
int node, int K, int maxN)
{
for (int i = maxN - 1; i >= 0; i--) {
if (K & (1 << i)) {
if (ancestor[node][i] == -1)
return -1;
node = ancestor[node][i];
}
}
return node;
}
int main()
{
int V = 7;
int maxN = log2(V) + 1;
// edge list
vector > edges
= { { 1, 2 }, { 1, 3 }, { 3, 4 },
{ 4, 5 }, { 4, 6 }, { 5, 7 } };
vector > graph(V + 1),
ancestor(V + 1, vector(maxN, -1));
// construct the adjacency list
for (auto edge : edges) {
graph[edge[0]].push_back(edge[1]);
}
// preprocessing
preprocess(graph, ancestor, V, maxN);
// queries
cout << findKthAncestor(ancestor, 7, 3, maxN) << "\n";
cout << findKthAncestor(ancestor, 5, 1, maxN) << "\n";
cout << findKthAncestor(ancestor, 7, 4, maxN) << "\n";
cout << findKthAncestor(ancestor, 6, 4, maxN) << "\n";
return 0;
}
Java
import java.util.*;
import java.lang.*;
class GFG {
// Depth First Search
static void dfs(int node, List> graph, List> ancestor, int parent) {
ancestor.get(node).set(0, parent);
for (int neighbor : graph.get(node)) {
dfs(neighbor, graph, ancestor, node);
}
}
// Method to initialize ancestor table
static void preprocess(List> graph, List> ancestor, int V, int maxN) {
dfs(1, graph, ancestor, -1);
for (int j = 1; j < maxN; j++) {
for (int i = 1; i <= V; i++) {
if (ancestor.get(i).get(j - 1) != -1)
ancestor.get(i).set(j, ancestor.get(ancestor.get(i).get(j - 1)).get(j - 1));
}
}
}
// Method to find Kth ancestor of node
static int findKthAncestor(List> ancestor, int node, int K, int maxN) {
for (int i = maxN - 1; i >= 0; i--) {
if ((K & (1 << i)) != 0) {
if (ancestor.get(node).get(i) == -1)
return -1;
node = ancestor.get(node).get(i);
}
}
return node;
}
public static void main (String[] args) {
int V = 7;
int maxN = (int) (Math.log(V) / Math.log(2)) + 1;
// edge list
List> edges = Arrays.asList(
Arrays.asList(1, 2), Arrays.asList(1, 3), Arrays.asList(3, 4),
Arrays.asList(4, 5), Arrays.asList(4, 6), Arrays.asList(5, 7)
);
List> graph = new ArrayList<>();
List> ancestor = new ArrayList<>();
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
ancestor.add(new ArrayList<>(Collections.nCopies(maxN, -1)));
}
// construct the adjacency list
for (List edge : edges) {
graph.get(edge.get(0)).add(edge.get(1));
}
// preprocessing
preprocess(graph, ancestor, V, maxN);
// queries
System.out.println(findKthAncestor(ancestor, 7, 3, maxN));
System.out.println(findKthAncestor(ancestor, 5, 1, maxN));
System.out.println(findKthAncestor(ancestor, 7, 4, maxN));
System.out.println(findKthAncestor(ancestor, 6, 4, maxN));
}
}
C#
using System;
using System.Collections.Generic;
class Program
{
static void dfs(int node, List> graph, List> ancestor, int parent)
{
ancestor[node][0] = parent;
foreach (int neighbor in graph[node])
{
dfs(neighbor, graph, ancestor, node);
}
}
static void preprocess(List> graph, List> ancestor, int V, int maxN)
{
dfs(1, graph, ancestor, -1);
for (int j = 1; j < maxN; j++)
{
for (int i = 1; i <= V; i++)
{
if (ancestor[i][j - 1] != -1)
{
ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
}
}
}
}
static int findKthAncestor(List> ancestor, int node, int K, int maxN)
{
for (int i = maxN - 1; i >= 0; i--)
{
if ((K & (1 << i)) != 0)
{
if (ancestor[node][i] == -1)
return -1;
node = ancestor[node][i];
}
}
return node;
}
static void Main()
{
int V = 7;
int maxN = (int)Math.Log(2, V) + 1;
// edge list
List> edges = new List>
{
new List { 1, 2 },
new List { 1, 3 },
new List { 3, 4 },
new List { 4, 5 },
new List { 4, 6 },
new List { 5, 7 }
};
List> graph = new List>(V + 1);
List> ancestor = new List>(V + 1);
for (int i = 0; i <= V; i++)
{
graph.Add(new List());
ancestor.Add(new List(new int[maxN]));
}
// construct the adjacency list
foreach (List edge in edges)
{
graph[edge[0]].Add(edge[1]);
}
// preprocessing
preprocess(graph, ancestor, V, maxN);
// queries
Console.WriteLine(findKthAncestor(ancestor, 7, 3, maxN));
Console.WriteLine(findKthAncestor(ancestor, 5, 1, maxN));
Console.WriteLine(findKthAncestor(ancestor, 7, 4, maxN));
Console.WriteLine(findKthAncestor(ancestor, 6, 4, maxN));
}
}
Javascript
// Depth First Search
function dfs(node, graph, ancestor, parent) {
ancestor[node][0] = parent;
for (let neighbor of graph[node]) {
dfs(neighbor, graph, ancestor, node);
}
}
// Method to initialize ancestor table
function preprocess(graph, ancestor, V, maxN) {
dfs(1, graph, ancestor, -1);
for (let j = 1; j < maxN; j++) {
for (let i = 1; i <= V; i++) {
if (ancestor[i][j - 1] !== -1)
ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
}
}
}
// Method to find Kth ancestor of node
function findKthAncestor(ancestor, node, K, maxN) {
for (let i = maxN - 1; i >= 0; i--) {
if (K & (1 << i)) {
if (ancestor[node][i] === -1)
return -1;
node = ancestor[node][i];
}
}
return node;
}
// Main function
function main() {
let V = 7;
let maxN = Math.floor(Math.log2(V)) + 1;
// edge list
let edges = [
[1, 2], [1, 3], [3, 4],
[4, 5], [4, 6], [5, 7]
];
let graph = Array.from({ length: V + 1 }, () => []);
let ancestor = Array.from({ length: V + 1 }, () => Array(maxN).fill(-1));
// construct the adjacency list
for (let edge of edges) {
graph[edge[0]].push(edge[1]);
}
// preprocessing
preprocess(graph, ancestor, V, maxN);
// queries
console.log(findKthAncestor(ancestor, 7, 3, maxN));
console.log(findKthAncestor(ancestor, 5, 1, maxN));
console.log(findKthAncestor(ancestor, 7, 4, maxN));
console.log(findKthAncestor(ancestor, 6, 4, maxN));
}
// Run the main function
main();
Python3
import math
# Depth First Search
def dfs(node, graph, ancestor, parent):
ancestor[node][0] = parent
for neighbor in graph[node]:
dfs(neighbor, graph, ancestor, node)
# Method to initialize ancestor table
def preprocess(graph, ancestor, V, maxN):
dfs(1, graph, ancestor, -1)
for j in range(1, maxN):
for i in range(1, V + 1):
if ancestor[i][j - 1] != -1:
ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1]
# Method to find Kth ancestor of node
def find_kth_ancestor(ancestor, node, K, maxN):
for i in range(maxN - 1, -1, -1):
if K & (1 << i):
if ancestor[node][i] == -1:
return -1
node = ancestor[node][i]
return node
if __name__ == "__main__":
V = 7
maxN = int(math.log2(V)) + 1
# edge list
edges = [[1, 2], [1, 3], [3, 4], [4, 5], [4, 6], [5, 7]]
graph = [[] for _ in range(V + 1)]
ancestor = [[-1] * maxN for _ in range(V + 1)]
# construct the adjacency list
for edge in edges:
graph[edge[0]].append(edge[1])
# preprocessing
preprocess(graph, ancestor, V, maxN)
# queries
print(find_kth_ancestor(ancestor, 7, 3, maxN))
print(find_kth_ancestor(ancestor, 5, 1, maxN))
print(find_kth_ancestor(ancestor, 7, 4, maxN))
print(find_kth_ancestor(ancestor, 6, 4, maxN))...