Easy fabejárás

Ma ezt a feladatot dolgozzuk fel:
http://www.spoj.com/problems/PYRA/

Miután elolvastuk a feladatot, próbáljuk kiszámolni, mit is kell kiírnunk? Egy elem szélessége a rajta levő elemeknek ( = a gyerekeinek) a szélességeinek az összege, plusz a gyerekeinek a száma plusz egy (a kihagyott üres helyek, mind egység széles, összesen ennyi van).
Ez a képlet kijön a levelekre is, ott nulla gyerek össz nulla szélesen, plusz egy az épp egy.

Fantasztikus, akkor csak felépítjük a gráfot, ami jön az inputon, irányítatlan gráfot fogunk építeni, mert mint ahogy a példából is látszik (van (0,1) és (2,0) is, 0 a gyökérelem), az élek irányát nem mondja meg az input.
Aztán ezt a fát a 0 csúcsból indulva egy bfs-sel felcímkézzük, rekurzívan, mert az időlimit azt mondja, hogy nagyon-nagyon ráérünk (lineáris futásidejű algoritmus, legfeljebb 25 darab egyenként legfeljebb tízezer csúcsú fán, ez pite). Közben szummázzuk is az értéket.

Sample megoldás itt. 0:25, ez bőven javítható, a C++ beépített konténerosztályok adnak egy kis overheadet, de nem arra játszunk versenyen, hogy a leggyorsabb kódot írjuk, hanem arra, hogy a leggyorsabban írjunk egy ACCEPT kódot, úgyhogy using namespace std, davaj.
Pár szó a kódról:

• mivel a gráfunk irányítatlan, fel kell címkézzük a csúcsokat -- visited tömb
• vizsgálhatnánk a bfs-be belépéskor is, hogy visited-e a node vagy sem, meg minden hívás előtt is. Általában azt javasolnám, hogy belépéskor első sorban tegyük ezt, de most azért nem, mert a bfs visszaad egy számot, amihez hozzáadunk egyet. Mondjuk persze akkor visszaadhatna -1-et is, és 0 lesz az összeg, de ez csak most jutott eszembe :D 
• emiatt a 0 csúcs visited értékét alapból 1-re kell állítsuk, a többiét meg 0-ra, mielőtt hívnánk a bfs-t a 0 gyökércsúcsra. (this costed me a WA :P :D ) Meghívjuk és az akkumulált totalSize értéket kiírjuk.

Minden versenyen van egy olyan feladat, amit csak oda kell adni a kódernek, hogy tessék, kódold le, míg a többiek megoldanak még egyet, a jobb lengyelek rendszerint tíz percen belül ezt azonosítják is és meg is oldják. Ennek a feladatnak a tanulsága maximum az, hogy ismerjük és használjuk az STL osztályokat: gráfot pl éllistával érdemes egy vector< deque< int > >-be rakni, ha a csúcsai 0-tól N-ig a számok, úgy a szomszédsági listákat konstans időben elérjük, a listákon a deque-eken az iterátor léptetése konstans, és az új él beszúrása is konstans idő, mást meg nem kell csinálnunk, tehát az adatszerkezet nagyon jó időigényt biztosít nekünk.
Hülyeség szomszédsági mátrixba rakni a dolgokat (általában egyébként az; egy kivétel talán, mikor iterált mátrixhatványozással oldunk meg tranzitív lezárást. Meg a Floyd-Warshall. Talán.)