Expedition
InterviewTime limit2sMemory limit512 MB
Each candidate forbids at most one other candidate; choose the largest subset where no included candidate's forbidden partner is also included.
- Level
Medium6 of 10
- Topics
- Graph, Greedy, Dynamic programming, Tree
- Solved
- No attempts yet
Problem
An expedition is being planned to a neighboring star system. There are candidates, numbered from 1 to , from whom the expedition members must be chosen. The organizers want to send as many candidates as possible.
The candidates were surveyed, and each could name at most one other candidate with whom they are not willing to go on the expedition. The survey result for candidate is an integer , equal to the number of a candidate with whom candidate is not willing to go, or if candidate is willing to go in any group.
Now the organizers must decide who will go on the expedition. They decided to choose the members so that if candidate is included and , then candidate is not included. The organizers want to choose the largest possible number of expedition members.
Write a program that, given the survey results, determines the maximum number of candidates that can be sent on the expedition.
Input
The first line contains the integer , the number of candidates ().
The next lines contain the survey results; the -th of these lines contains the result of candidate , an integer ( or , ).
Output
Output a single integer on one line: the maximum number of candidates that can be sent on the expedition.