All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is a private detective. He was asked to investigate a case of murder in the city of Frangton.
Chef arrived in Frangton to find out that the mafia was involved in the case. Chef spent some time watching for people that belong to the clan and was able to build a map of relationships between them. He knows that a mafia's organizational structure consists of a single Don, heading a hierarchical criminal organization. Each member reports exactly to one other member of the clan. It's obvious that there are no cycles in the reporting system of the mafia.
There are N people in the clan, for simplicity indexed from 1 to N, and Chef knows who each of them report to. Member i reports to member Ri.
Now, Chef needs to identfy all potential killers to continue his investigation. Having considerable knowledge about the mafia's activities, Chef knows that the killer must be a minor criminal, that is, one of the members who nobody reports to. Please find the list of potential killers for Chef. Since Don reports to nobody, his Ri will be equal to 0.
The first line of input contains one integer N.
Next line has N space-separated integers, the ith integer denotes Ri — the person whom the ith member reports to.
Output a list of space-separated integers in ascending order — the indices of potential killers.
- 1 ≤ N ≤ 105
- 1 ≤ Ri ≤ N except for Don, whose Ri equals to 0.
- It is guaranteed that there are no cycles in the reporting structure.
- Subtask #1 [50 points]: N ≤ 10000
- Subtask #2 [50 points]: No additional constraints
Input: 6 0 1 1 2 2 3 Output: 4 5 6
The reporting structure:
|Tags||cakewalk cenadar feb16 hashing tree|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.