## Bulgarian OI '09 P2 - Boxen

View as PDF

Points: 12
Time limit: 0.6s
Memory limit: 32M

Problem type
##### 2009 Bulgarian Olympiad in Informatics

The programmer Pesho is a very thrifty person. The money which he earns from website design he stores in money boxen , labeled by the integers from to . The intention of Pesho is to buy a new super-computer. In order to avoid the temptation to spend the money on rubbish, before the necessary sum is collected, he dropped all keys of the money-boxen in a random way inside the boxen themselves.

Fortunately, Pesho marked on a sheet of paper where the key for each money-box is stored. Now, the necessary money is finally collected and Pesho has to open all the money-boxen to take the money.

Unfortunately, no keys are available: Pesho must break the boxen! Pesho doesn't like breaking things, so he'd like to break as few boxen as possible. He realized that when a broken money-box contains a key of another money-box then the second money-box could be simply unlocked.

Write a program to determine the minimal number of money-boxen that have to be broken in order to collect all the stored money.

#### Input Specification

The program has to solve two test cases for each run. Each test case starts with a line containing the number of money-boxen. Then lines follow with one integer from to - on the th line is the box in which the key for the th box is stored.

#### Output Specification

Output the minimal number of boxen that must be broken. Separate the numbers with a space.

#### Sample Input

4
2
1
2
4
3
3
3
3

#### Sample Output

2 1

#### Explanation

In the first test case, the 4th box must be broken, because it contains its own key. Then, you can simply break the 1st box - it contains the key for box 2, which contains the key for box 3.

In the second case, you can just break box 3 to enter everything.

• commented on Dec. 5, 2020, 1:05 p.m.

I tried to use vector to store my graph, but I got WA on 4 cases. I only got AC by switching to unordered_map. Does anyone know why this happened?

• commented on Dec. 5, 2020, 1:34 p.m.

You clear the vector for each test case but don't resize it. The reason using a map worked is because maps don't require you to allocate the memory locations before you access them. I would still recommend using vectors as oppose to maps since their time complexity is better.