The family tree of Bob

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 Q query and N family members. They have to just print the kth 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 kth 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 3
Output:
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, 12);
        addEdge(adj, 23);
        addEdge(adj, 34);
        addEdge(adj, 25);
        addEdge(adj, 16);

        logn = (intMath.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[][] = { { 41 }, { 43 }, { 61 }, { 51 }, { 53 } };

        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>> gint uint v) {
        // undirected graph
        g.get(u).add(v);
        g.get(v).add(u);
    }

    static void preprocessing(int uint 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 uint 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