Državno natjecanje iz informatike 2021. / Prva podskupina (1. i 2. razred) – drugi dan natjecanja - 3. zadatak

Zadan je usmjereni graf u kojemu iz svakog vrha izlazi točno jedan brid u neki drugi vrh.

Koliki je najmanji broj vrhova koje iz toga grafa treba obrisati tako da u grafu ne ostane nijedan put duljine dva; drugim riječima, tako da ne postoje neka tri (ne nužno sva različita) vrha a, b, c s bridovima a → b i b → c?

Ulazni podaci

U prvom je retku prirodan broj n (3 ≤ n ≤ 100 000), broj vrhova grafa. Vrhovi su označeni brojevima od 1 do n.

U i-tom od idućih n redaka prirodan je broj j (i 6= j) koji predstavlja brid i → j.

Izlazni podaci

U jedini redak ispišite traženi najmanji broj vrhova koji treba obrisati.

Primjer zadatka

Ulaz

4
3
3
4
3

Izlaz

1

Objašnjenje

Pojašnjenje prvog probnog primjera: Možemo obrisati vrh 3. Alternativno, možemo obrisati vrh 4

Ulaz

5
4
5
4
2
1

Izlaz

2

Objašnjenje

Pojašnjenje drugog probnog primjera: Možemo obrisati bilo koji od sljedećih parova vrhova: (1, 2),

(1, 4), (2, 4), (2, 5), (4, 5).

Ulaz

6
2
1
2
6
4
5

Izlaz

2

Objašnjenje

Pojašnjenje trećeg probnog primjera: Možemo obrisati bilo koji od sljedećih parova vrhova: (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6).