Feladat: S.67 Korcsoport: - Nehézségi fok: -
Füzet: 2011/december, 554 - 555. oldal  PDF  |  MathML 
Témakör(ök): Programozás, algoritmusok

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Régen, amikor a számítógép-hálózatok többnyire még koaxiális kábelekből és BNC csatlakozókból álló láncok voltak, a Pokoli Rendszergazda egyik kedvenc hobbija volt a hálózati topológia menet közbeni átalakítása, és az ezt követő felhasználói reakciók monitorozása.
Sajnos az újabb és újabb hálózatépítési módszerek elterjedésével a fenti szórakozás sokat vesztett értékéből, így a Pokoli Rendszergazda elhatározta, hogy a régi szép idők emlékére hobbiját virtuális környezetben újraéleszti. Minket kért fel annak a programkomponensnek a kifejlesztésére, amely a hálózat állapotát, illetve a felhasználói visszajelzéseket szimulálja.
A szimulátor egy N darab összeköttetés nélküli számítógépből álló ,,üres'' hálózatból indul ki, majd összesen M darab hálózatépítési és diagnosztikai műveletet vár. Feladata, hogy az egyes műveletekről rendre eldöntse, hogy azok megvalósíthatóak-e, és a megvalósítható hálózatépítési műveleteket sorra végrehajtsa.
A hálózatépítési műveletek részletesen a következők:

•add <A> <B>
ahol 1≤A≠B≤N a két számítógép sorszáma, melyek között új (kétirányú) összekötést kell kiépíteni. A művelet megvalósítható, ha jelenleg mindkét számítógéphez legfeljebb 1 kábel csatlakozik, és az új összekötés nem eredményez kört.
•remove <A> <B>
ahol 1≤A≠B≤N a két számítógép sorszáma, melyek közötti közvetlen összekötést meg kell szüntetni. A művelet megvalósítható, ha A és B között vezet kábel.

Az alábbi diagnosztikai művelet pedig annak vizsgálatára szolgál, hogy az adott felhasználóktól várható-e visszajelzés a közeljövőben:
•ping <A> <B>
ahol 1≤A≠B≤N a két számítógép sorszáma, melyek közötti elérhetőséget vizsgáljuk. A művelet megvalósítható, ha A és B között vezet út a hálózatban.

Mindhárom műveletre a megvalósíthatóságtól függően ,,yes'', illetve ,,no'' választ kell adni.
A program 2≤N≤1000000 és 0≤M≤1000000 értékét a standard bemenet első sorában kapja, egyetlen szóközzel elválasztva. Az ezt követő M darab sor pedig egy-egy műveletet ír le a fenti formátumban.
A standard kimenetre szintén pontosan M darab sor kerüljön, minden sorba rendre a megfelelő művelet eredménye. A maximális pontszám eléréséhez a programnak legfeljebb néhány másodpercen belül le kell futnia a legnagyobb bemenetekre is.
 
 

Beküldendő egy tömörített s67.zip állományban a program forráskódja (s67.pas, s67.cpp, ...) az .exe és más, fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s67.txt, s67.pdf, ...), amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrás melyik fejlesztő környezetben fordítható.