Tanár vagy a Kis Kódolók óvodában. Az csoportodba N gyermek jár, 1-től N-ig terjedő azonosítókkal számozva. Minden gyereknek van egyetlen Örökre Legjobb Barátja (ÖLeB), és tanárként ismered is ezeket a barátságokat. Az ÖLeB nem szimmetrikus, előfordulhat, hogy X örökre legjobb barátja Y, de Y-é nem X. Meg kell tervezned egy olyan foglalkozást, ahol az óvodások körben ülve hajtanak végre egy feladatot. Tapasztalatból tudod, hogy a gyerekek jobban dolgoznak, ha örökre legjobb barátjuk mellett ülhetnek, ezért szeretnéd a lehető legnagyobb kört kialakítani, ahol mindenki az örökre legjobb barátja mellett ül. Az mindegy, hogy jobbra vagy balra ül a legjobb barát. Előfordulhat, hogy nem tudod az összes gyereket leültetni a kör mentén, de szeretnéd a lehető legnagyobb kört kialakítani.
FeladatÍrjunk programot, ami megadja, hogy legfeljebb hány gyerek ültethető le egy kör mentén, a megadott feltételeknek megfelelően.
BemenetA bemenet első sora a tesztesetek T számát adja meg, 1 <= T <= 100. Ezután T teszteset következik. Minden teszteset első sora a diákok N számát adja meg, majd N diákazonosító következik: F1, F2, ..., Fn, ahol Fi az i. diák örökre legjobb barátjának azonosítója. Kis tesztekre 3 <= N <= 10, nagyokra 3 <= N <= 1000. Feltehetjük, hogy Fi <> i, vagyis senki nem legjobb barátja önmagának.
KimenetMinden tesztesetre meg kell adni a kialakítható legnagyobb kör méretét.
Példa
Tesztadatok
CímkékA feladat forrása: Google Code Jam 2016 Round 1A, https://code.google.com/codejam/contest/4304486/dashboard#s=p2
Algoritmusok: mélységi bejárás
|
Programozás > Feladatok >