Find Root of Tree
EasyPractice library · +10 XPtreesarrays
A tree is given using a parent array representation. The array P of size N describes the tree where P[i] is the parent of node i. The root of the tree is the unique node that does not have a parent (its parent is represented by -1). Given the parent array P, find and print the index of the root node.
Input
The first line contains a single integer N, the number of nodes in the tree. The second line contains N space-separated integers P_0, P_1, ..., P_{N-1}, where P_i is the parent of node i. The root node has parent -1.
Output
Print a single integer, the index of the root node.
Constraints
1 <= N <= 1000 -1 <= P_i < N for all i where P_i != -1.
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 -1 0 0 1 1
Output
0
The parent array is [-1, 0, 0, 1, 1]. Node 0 has parent -1, so it is the root.
Example 2
Input
1 -1
Output
0
A tree with a single node. Node 0 is the root.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 -1 0 0 1 1
Example 2 input
1 -1