Given a rooted tree with N nodes, what nodes are leaves?
A leaf is a node with no children when we walk down the tree from the root node (the Don).
EXPLANATION:
We are given a list R of N integers, where element R_i denotes to whom person i reports to.
For every person P, we want to know if there is any other person reporting to P.
Subtask1
A simple approach is: for every person i, search the given list to see if anyone reports to i.
for i from 1 to N do
for j from 1 to N do
if R[i] equals i then
person j reports to i and is not a leaf
if person i does not have any reports, add to solution
For every person, we do a linear scan on the given list. It’s clear that the time complexity of this approach is O(N^2) which was enough for the first subtask but not for the second.
Subtask 2
We can do better. We really just want to know for every person P if there is anyone that reports to P.
There are several ways to do this efficiently. A simple way is to use a boolean array, e.g. has_reports, and use this to store if node i has anyone reporting to it. We can process the given list only once and mark has_reports[i] to true when someone reports to i. Sample pseudo-code:
Initialise has_reports array to false in all positions
for i from 1 to N do
has_children[R[i]] = true
for i from 1 to N do
if has_children[i] is true then
print i
We only process the list once and use an array to mark the reports information. So the time complexity of this approach is O(N). Also, the space complexity is O(N).
i’m still not getting the question what is the input we’re taking in second line?
whats the meaning of this line-
“Next line has N space-separated integers, the ith integer denotes Ri — the person whom the ith member reports to.”
What’s wrong with this code . This code checks which node have 0 child i.e leaf should be accepted acc. to me can some one have a look and tell me what’s wrong ?
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
vector<int> tree[MAX];
int child[MAX];
void dfs(int u,int p){
for(int v : tree[u]){
if(v==p){
continue;
}
else{
dfs(v,u);
child[u] += child[v]+1;
}
}
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cout.tie(NULL);
int n; cin>>n;
int u,v;
cin>>u;
memset(child,0,sizeof(child));
for(int i=2;i<=n;i++){
cin>>u;
v=i;
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
if(child[i]==0){
cout<<i<<" ";
}
}
return 0;
}