How i convert array to adjacency list of tree?

June 2, 2023

This is problem:

Write a program that determines for two nodes of a tree whether the first one is a parent of another.

Input data

The first line contains the number of vertices n (1 ≤ n ≤ 10^5) in a tree. The second line contains n numbers, the i-th one gives the vertex number of direct ancestor for the vertex i. If this value is zero, then the vertex is a root of a tree.

The third line contains the number of queries m (1 ≤ m ≤ 10^5). Each of the next m lines contains two different numbers a and b (1 ≤ a, b ≤ n).

Output data
For each of the m queries print on a separate line number 1, if the vertex a is one of the parents of a vertex b, and 0 otherwise.

Example tree

Input example #1

6
0 1 1 2 3 3
5
4 1
1 4
3 6
2 6
6 5

Output example #1

Link: Problem

I tried for hours but i couldn’t convert the second part of the input into an adjacency matrix. This is all I need. I have found the other parts of solution.

My soluton(C++):

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<vector<int>> g;
vector<int> time_in,time_out;
int Time=0;
void dfs(int node,int parent){
    time_in[node]=++Time;
    for(int &to:g[node]){
        if(to!=parent){
                dfs(to,node);
        }
    }
    time_out[node]=++Time;// or  time_out[node]=Time;
}
bool isAnchestor(int anch,int node){
    return time_in[anch]<=time_in[node] and time_out[anch]>=time_out[node];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    time_in.resize(n+1);
    time_out.resize(n+1);
    g.resize(n+1);
    vector<int> anchestors(n+1);
    for(int i=1; i<=n; ++i){// I am thinking: the anchestors is sorted.
            cin>>anchestors[i];

            //
    }

    int start=anchestors[0];


    dfs(start,1);


    int q,u,v;
    cin>>q;
    while(q--){
        cin>>u>>v;
        cout<<isAnchestor(u,v)<<'\n';// The anchestor of v is u. //(u,v)-->(a,b)
    }
    return 0;
}

>Solution :

In your code, you have a for loop that reads in the ancestor values for each vertex. You can use this loop to construct the adjacency matrix. For each vertex i, you can add an edge between i and its ancestor anchestors[i] if anchestors[i] is not 0 (indicating that i is not the root). Here’s an example of how you can modify your for loop to construct the adjacency matrix:

for(int i = 1; i <= n; ++i) {
    cin >> anchestors[i];
    if(anchestors[i] != 0) {
        g[i].push_back(anchestors[i]);
        g[anchestors[i]].push_back(i);
    }
}

This will add an edge between each vertex and its ancestor in the adjacency matrix g.