Iskolahálózat
Néhány iskola össze van kapcsolva egy hálózatba. Mindegyiknek van egy listája azokról az iskolákról, akiknek továbbad szoftvereket.
Ha egy iskola kap egy új szoftvert, akkor továbbadja a listáján lévő összes iskolának.
Ha az A iskolának a B iskola a listáján van, akkor nem biztos, hogy a B iskolának a listáján ott van A.
A)
Írjunk programot, amely meghatározza, hogy minimum hány iskolának kell odaadni egy szoftvert, hogy a hálózat összes iskolájához eljusson!
B)
Biztosítani szeretnénk, hogy egy tetszőleges iskolának odaadva a szoftvert, az összes iskolához eljusson.
Ehhez az iskolák listáit kibővíthetjük további elemekkel. Határozzuk meg, hogy ennek eléréséhez minimum hány elemet kell összesen hozzáadni a listákhoz!
Bemenet:
A bemeneti fájl első sora az iskolák N (1<=N<=10000) számát tartalmazza. Az iskolákat az első N pozitív egész számmal azonosítjuk.
A következő N sor mindegyike egy-egy iskola listáját tartalmazza. A listák végén egy 0 szerepel (üres lista sorában egyetlen 0 szerepel).
Kimenet:
A kimeneti fájl két sora az A és B részfeladat megoldását tartalmazza.
Példa:
| Iskola.be | Iskola.ki |
|
5
2 4 3 0
4 5 0
0
0
1 0
|
1
2
|
(Nemzetközi informatikai diákolimpia 1996)
Tesztfájlok: