Az előző részben a 2014/15. évi Informatika OKTV Döntő 3. feladatára (Családfa, elérhető pl. http://nemes.inf.elte.hu/nemes_archivum.html#2015) adtunk megoldást. Az algoritmus minden gyermektelen személytől kiindulva bejárta a szülő‐gyermek kapcsolatok által létrehozott gráfot, és megtalálta a közös ősöket. Mivel a feladatban akár 10 000 személy is szerepelhetett, ezért megpróbáltuk kiszámítani, hogy milyen nagyságrendű az algoritmus lépésszáma, nehogy nagy bemenetekre túllépjük az időkorlátot. Arra jutottunk, hogy a személyek $N$ számának négyzetével arányos lépésszámú algoritmust készítettünk. A cikk végén kértük, hogy az olvasók maguk is töprengjenek jobb megoldáson, és írják meg a KöMaL honlapján működő Fórumban az Informatika OKTV témához.
A kisebb lépésszámú megoldás megtalálásához a futásidő becslése hasznos, mert közben alaposan elemezzük az algoritmusunkat, így láthatjuk, hogy melyek azok a részek, ahol érdemes javítani, hatékonyabb megoldást keresni. Szembetűnő, hogy a megoldásunk többször is bejárja azokat a részgráfokat, amelyek elérhetők egy-egy gyermektelen csúcstól. Próbáljuk meg elkerülni a gráf többszöri bejárását! Ez csak úgy lehetséges, ha minden érintett szülőnél nyilvántartjuk, hogy mely gyermektelenektől juthatunk el hozzá. A feladathoz mellékelt példában (ld. előző rész vagy a feladat linkje) induljunk ki a 4-es csúcstól, de csak a szülőkig haladjunk előre, és jegyezzük föl a 3-as és 8-as csúcshoz, hogy oda a 4-estől el lehet jutni. Ezután az 5-ös személy szüleivel folytassuk, és jegyezzük föl a 8-as és 9-es csúcshoz, hogy oda az 5-östől el lehet jutni. Amennyiben az összes gyermektelentől elértünk a szüleihez, és tároltuk a gyermekeik sorszámát, akkor ezután a szülőktől kell folytatnunk a bejárást. Most már azt kell kideríteni, hogy tőlük mely csúcsokba lehet eljutni. Tőlük folytathatjuk az előbbi módszerrel, de ügyeljünk arra, hogy egy csúcsból csak akkor térjünk át a szülő csúcsokhoz, ha a csúcshoz vezető összes gyermektől már odaértünk, és megjegyeztük, hogy mely gyermektelenek leszármazottai.
Az első megoldáshoz hasonló, de a eddigiektől eltérő vezérlésű bejárás kezd körvonalazódni. Minden lépésben egy gyermektől lépünk tovább a két szülőhöz, de csak olyan gyermektől, amelynek korábban minden gyermekéhez már eljutottunk. A gyermeknél lévő információt ‐ vagyis az ő gyermektelen gyermekeinek sorszámát ‐ átadjuk a két szülőnek. Így fokozatosan eljutunk az ősökhöz, és a bejárás végére kiderül, hogy mely ősöknél szerepel az összes gyermektelen sorszáma. A gráf bejárása tehát úgy történik, hogy minden egyes lépésnél egy olyan csúcsot választunk, amelyhez az összes oda vezető élt már bejártuk. Ilyen csúcs biztosan van az elején, tehát a sorba először a gyermektelenek kerülnek, majd az ő szüleik közül azok, amelyekhez már minden gyermekétől eljutottunk, és így tovább.
Nézzük, hogy milyen módon tároljuk a bejárás alatt az adatokat. Ha tudjuk, hogy $g$ számú gyermektelen van, akkor $N-g$ számú szülőhöz kell fölvenni $g$ számú logikai értéket, amely megadja, hogy az adott szülőt mely gyermektelenektől lehet elérni. A legegyszerűbb esetben $g\cdot \left(N-g\right)$ egybájtos szám tárolása szükséges. Ismét a számtani-mértani közepek közötti összefüggést alkalmazva $N^2/4$ logikai értékünk lesz, vagyis a legnagyobb elemszám esetén is 25 MiB alatti a helyfoglalás. Ez jelentős memóriaterület a korábban fölvett 10 KiB nagyságrendű adatokhoz képest.
Természetesen kevesebb hely is elegendő lenne, ha pl. minden csúcsnál egy listába fűznénk a hozzá vezető gyermektelenek sorszámát. De így minden él bejárásakor össze kellene vetni az él által összekapcsolt szülő és a gyermek gyermektelen listáit, ami a tömbös változatnál nagyobb lépésszámú algoritmust eredményezne. Vagy megtehetnénk, hogy bittömböket használunk, így 8-adára csökkenhető a tárolás. Megtehetnénk még azt is, hogy dinamikusan kezeljük a tömböket, vagyis mindig csak annyi tömbnek foglalunk helyet, amelyben tényleg van adat, hiszen a még el nem ért csúcsokban a táblázat csupa hamis értéket tartalmaz, és a már bejárt gyermekek adataira nincs is szükség. De egyelőre úgy számoltunk, hogy a memóriakorlát alatt vagyunk, ezért alkalmazzunk egyszerűbb adatszerkezetet. A legegyszerűbb persze egy $N\times N$-es tömb volna, de azzal már túllépnénk a memóriakorlátot.
Legyen tehát egy $N^2/4$ méretű gy tömbünk, amelyben logikai értékek vannak. Az első $g$ darab szám megadja, hogy a bejárás során érintett első szülőhöz mely gyermektelenektől lehet eljutni. A második $g$ darab szám megmutatja, hogy a második szülő mely gyermektelenektől érhető el stb. A gy tömb mellé szükségünk van még két másik táblázatra, amelyek megadják, hogy az adott sorszámú csúcs hányadik gyermektelen, illetve hányadik szülő. Ezekkel a számokkal már megcímezhetjük a gy tömb megfelelő elemét. Példaként legyen a feladathoz mellékelt gráf, amelyben négy gyermektelen van. Vegyünk föl egy $N$ méretű ind tömböt, amely egyben tartalmazza a két táblázatot, hiszen egy csúcs vagy szülő, vagy gyermektelen. A tömb 4, 5, 6 és 7 sorszámú eleme rendre 1, 2, 3 és 4, mivel ez a négy csúcs a négy gyermektelent jelöli. A szülők az 1, 2, 3, 8, $\text{...}$, 20 sorszámúak, az ő értékük a gy tömbben rendre 1, 2, 3, 4, $\text{...}$, 16. Például a 8-as sorszámú (sorrendben 4. szülő) gyermeke az 5-ös (sorrendben 2.) gyermektelen, vagyis a táblázatában gy[(ind[8]-1)*g+ind[5]], azaz gy[(4-1)*4+2], tehát gy[14] értéke igaz. Általában tehát az szk-adik szülő gyk-adik gyermektelentől való elérhetőségét a gy[(ind[szk]-1)*g+ind[gyk]] érték adja meg.
Nézzük akkor a feladatot ‐ remélhetőleg hatékonyabban ‐ megoldó Családfa2 algoritmust. Az adatok beolvasása és az él tömb létrehozása után több előkészítésre is szükség van. A bejárás minden lépésben egy olyan csúcsot választ, amely gyermektelen, vagy olyat, amely szülő, de már minden gyermekétől eljutottunk hozzá. Ez utóbbi megállapításához szükségünk van minden csúcsban arra az információra, hogy hány olyan él vezet hozzá, amelyet még nem jártunk be. Ezt a számot tárolhatjuk egy tömbben, amelynek megfelelő értékeit a bejárás közben mindig csökkentjük. Így ebben a táblázatban a 0 értékű, még fel nem dolgozott csúcsokon mindig folytatódhat a bejárás. A jártunk tömb helyett egy egészeket tároló gysz táblázatunk lesz, amely megmutatja, hogy hány gyerektől kell még elérnünk az adott csúcshoz. A gyermektelenek esetében az érték már kezdetben is 0. Az így létrehozott tömbök adatai alapján kitöltjük az ind táblázatot is, és feltöltjük a gy tömböt hamis értékekkel, hiszen még nem értünk el egyetlen csúcsot sem.
A bejárás során csak a szülőkkel rendelkező csúcsokból kell az éleken végighaladni, ezért tároljuk a szülő nélküli tulajdonságot is minden személynél egy szn logikai tömbben. Ez az érték ugyan azonnal látszik az él táblázatból, de mégis érdemes külön nevet adni neki. Ők a lehetséges közös ősök, azok a személyek, akiket biztosan nem kell a sorba elhelyezni. Az adatok beolvasása után, de még a bejárás előtt gyűjtsük össze a bejáráshoz szükséges információkat és adjuk meg a fenti adatok kezdőértékeit: