In this HackerEarth Restoring trees problem solution You are given the start and finish times of a DFS (Depth-first search) traversal of the vertices that are available in a rooted tree. Your task is to restore the tree.


HackerEarth Restoring trees problem solution


HackerEarth Restoring trees problem solution

#include<bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, st[N], fn[N], rev[N], P[N];
void Solve(int v)
{
int nw = st[v] + 1;
int u = rev[nw];
for (; nw < fn[v]; nw = fn[u], u = rev[nw])
P[u] = v, Solve(u);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &st[i]), rev[st[i]] = i;
for (int i = 1; i <= n; i++)
scanf("%d", &fn[i]);
Solve(rev[0]);
for (int i = 1; i <= n; i++)
printf("%d ", P[i]);
printf("\n");
return (0);
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 14;

int n, st[maxn], en[maxn], per[maxn], ans[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> st[i];
for(int i = 0; i < n; i++)
cin >> en[i];
iota(per, per + n, 0);
sort(per, per + n, [](int i, int j){ return st[i] < st[j]; });
int p = -1;
for_each(per, per + n, [&p](int &i){
while(p != -1 && en[p] < en[i])
p = ans[p];
ans[i] = p;
p = i;
});
for(int i = 0; i < n; i++)
cout << ans[i] + 1 << ' ';
cout << '\n';
}