Bob wants to know about his ancestors, therefore, he draws a graph of his family. In that graph, root is the eldest-known family member. The leaf node is a member who has no children.
You are given a query and family members. They have to just print the ancestors with respect to that query. A member can have only one parent.
Note: Print -1 if the query is incorrect, that is, if the ancestor is not available. The root of the tree is 1.
Example:
Input:6 5 1 2 2 3 3 4 2 5 1 6 4 1 4 3 6 1 5 1 5 3Output:3 1 1 2 -1
Approach
Java
import java.util.ArrayList;import java.util.Arrays;public class TheFamilyTreeOfBob {static int logn;static int[][] up;static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();public static void main(String[] args) {int n = 6;int q = 5;for (int i = 0; i <= n; i++)adj.add(new ArrayList<>());addEdge(adj, 1, 2);addEdge(adj, 2, 3);addEdge(adj, 3, 4);addEdge(adj, 2, 5);addEdge(adj, 1, 6);logn = (int) Math.ceil(Math.log(n) / Math.log(2));up = new int[n + 1][logn + 1];for (int i = 0; i <= n; i++)Arrays.fill(up[i], -1);preprocessing(1, -1);StringBuilder sb = new StringBuilder("");int a2D[][] = { { 4, 1 }, { 4, 3 }, { 6, 1 }, { 5, 1 }, { 5, 3 } };int i = 0;while (q-- > 0) {int u = a2D[i][0];int k = a2D[i][1];i++;int ans = kth(u, k);sb.append(ans + "\n");}System.out.println(sb.toString().trim());}private static void addEdge(ArrayList<ArrayList<Integer>> g, int u, int v) {// undirected graphg.get(u).add(v);g.get(v).add(u);}static void preprocessing(int u, int p) {up[u][0] = p;for (int i = 1; i <= logn; i++) {if (up[u][i - 1] != -1) {up[u][i] = up[up[u][i - 1]][i - 1];}}for (int v : adj.get(u))if (v != p)preprocessing(v, u);}static int kth(int u, int k) {for (int i = logn; i >= 0; i--) {int bit = ((k >> i) & 1);if (bit == 0)continue;if (up[u][i] != -1) {u = up[u][i];} else {return -1;}}return u;}}
No comments:
Post a Comment