Nemes Tihamér OKSzTV'97

Feladat: Bandák (66 pont)

Johannesburg rendőrsége az összes bűnözőt ismeri a városban. Tudják, hogy két bűnöző akkor tartozik ugyanabba a bandába, ha legalább egyszer közösen követtek el bűncselekményt (a bandák tagjai közül csak a közös bűncselekményt elkövetők ismerik egymást).

A bűnözőket a nevük helyett a sorszámukkal azonosítják (1-től kezdve, folyamatos sorszámozással). A rendőrség a BANDAx.BE szöveges állományban tárolja az egy bandába tartozó bűnözők sorszámát. Az állomány első sorában a bűnözők száma (maximum 50), minden további sorában (maximum 100) pedig két bűnöző sorszáma van (egyetlen szóközzel elválasztva), akik közösen követtek el bűncselekményt. Lehetnek olyan magányos bűnözők is, akik egyetlen bandának sem tagjai (ahol bandákkal kapcsolatos eredményt kérünk, ott őket nem szabad figyelembe venni).

Példa:

Készíts programot, amely a BANDAx.KI állományba és a képernyőre kiírja egy-egy sorba az alábbiakat. (Ha valamelyik megoldás több számból áll, akkor közéjük egy-egy szóközt kell írni. Egy üres sort akkor is írj ki az állományba és a képernyőre, ha az adott részfeladattal nem fogalkoztál!)

A. A magányos bűnözők sorszámát. (A fenti példa szerint egyedül a 7. magányos.)

B. A bandák számát. (A példában 2, hiszen az egyikbe tartozik az 1., 2., 3. és 4., a másikba pedig az 5. és 6.; a magányos bűnözők nem alkotnak bandát.)

C. Az egyes bandák legtöbb kapcsolattal rendelkező tagját. (A példában 1., illetve 5. vagy 6.)

D. A legnagyobb banda tagjainak számát. (A fenti példa esetén 4, mivel az 1., 2., 3. és 4. bűnöző van egy bandában.)

E. Az egyes bandák kulcsembereit, azaz azokat, akiket börtönbe zárva a bandák a lehető legtöbb független részre esnek szét. (A példában 1., illetve 5. vagy 6.)

F. A biztonságosan szervezett bandák számát, azaz olyanokét, amelyekből a rendőrség nem tud úgy letartóztatni egyetlen bűnözőt, hogy a banda több részre essen szét. (A példában 0, hiszen az 1. bűnöző letartóztatásával az 1. banda magányos bűnözőkre esik szét, a kéttagú bandák egyik tagjának letartóztatásával pedig a másik tag ugyancsak magányos bűnözővé válik.)

G. A kockázatosan szervezett bandák számát, azaz olyanokét, amelyekben csak a főnök ismer mindenkit, és ezért az ő letartóztatása esetén a banda magányos bűnözőkre esik szét. (A példában 2, hiszen az 1. bűnöző letartóztatásával a 2., 3. és 4. magányos bűnözővé válik, a kéttagú bandák pedig mind ilyenek.)

H. A totálisan szervezett bandák számát, azaz olyanokét, amelyekben mindenki ismer mindenkit. (A példában 1, hiszen a kéttagú bandák mindig ilyenek.)