Adva van egy társaság, ahol közvetlen ismerősnek nevezünk két embert, ha ismerik egymást. Két ember, A és B közvetett ismerősök, ha közvetlenül nem ismerősök, de van olyan B1,B2,…,Bk személy(ek) a társaságban, hogy A és B1, B1 és B2, …, Bk és C közvetlen ismerősök. Ismerős csoportnak nevezzük a személyek egy olyan halmazát, ahol mindenki mindenkinek közvetlen vagy közvetett ismerőse.
Adva van egy társaság, amely egyetlen ismerős csoportból áll. A társaság közepének nevezzük azt a személyt vagy személyeket, akiknek a társaságból való eltávozása esetén a társaság a legtöbb ismerős csoportra esne szét.
Feladat:
Határozzuk meg a társaság közepét.
Bemenet:
A társaságbeli személyeket 1000-nél kisebb pozitív egészszámokkal azonosítjuk. A bemenet első sora a tesztesetek számát tartalmazza, majd ezt követik a tesztesetek. Egy teszteset a következő formátumú. A teszteset első sorában a közvetlen ismeretségek N>0 száma szerepel. Ezután N számpár következik, amelyek megadják a közvetlen ismeretségeket, ahol a számpárok tagjai a társaság személyeinek azonosítására szolgáló számok.
Kimenet:
Minden tesztesetre adjuk meg a társaság közepébe tartozó személyek azonosítóinak a felsorolását!
(Nagy Tibor)