Párosítás

Egy versenyre jelentkezett N ember. Bármely két ember vagy ismeri egymást, vagy nem (feltesszük, hogy ha A ismeri B-t, akkor B is ismeri A-t). Kérdés, be tudjuk-e a résztvevőket két csoportba osztani úgy, hogy egy csoporton belül ne legyenek ismerős párok? Ha igen, adjunk meg egy lehetséges csoportosítást, ha nem, akkor írjuk ki, hogy nem létezik ilyen csoportosítás.

Bemenet:

Az INPUT.TXT állományban egymás után több verseny adatai szerepelnek. Egy verseny estén először egy N érték található, ennyi ember jelentkezett a versenyre, az embereket 1-től, egyesével adott sorszámmal azonosítjuk, majd számpárok következnek, melyek az ismerősöket adják meg. A 0 0 számpár jelenti az ismerősök megadásának végét. Ha N=0, akkor nincs több adat a fájlban.

Kimenet:

Írjuk az eredményeket az OUTPUT.TXT nevű állományba! Vagy adjunk meg egy lehetséges csoportosítást, vagy írjuk ki, ha nem létezik. A csoportokban a tagok azonosítóját nagyság szerint növekvően kell felsorolni! Egy feladathoz több lehetséges csoportosítást is találhatunk, elég egyet kiírni.
 

(Új algoritmusok 22.2-6 nyomán

Tesztfájlok:

t0.txt

t1.txt

t2.txt

t3.txt

t4.txt