Nie rozumiem pewnej linijki własnego kodu

Question

Siema, niedawno zakładałem wątek odnośnie tego zadania, lecz teraz przychodzę z czymś innym. Zacząłem tak sobie na kartce rysować jakieś proste przykłady, żeby może spostrzc ewentualne niedorobienia w algorytmie, lecz jak się później okazało, że myśl algorytmu była dobra, tylko jak to bywa w życiu - wykonanie do bani. Wracając do tematu, po kilku minutach tak bez żadnego powodu wpadłem na pewien pomysł i spróbowałem go zaimplementować. Jak się później okazało, to rozwiązało wszystkie błędy i teraz program przechodzi na 100%. Zastanawia mnie tylko to, czemu to działa, wsensie czemu bez tego program dawał mi tylko 80%(, gdzie 20% uciekało, ze względu na błędną odp)?

Jeśli chodzi o tą zmianę w kodzie, to 64. linia z takiej:

if (!con)

stała się taką:

if (!con or vis.size() != nei.size())

Zadanie: https://www.docdroid.net/ieoxJSw/wzr-pdf

Kod: https://ideone.com/vdP0Bj

Comments

Porównanie (!= też) ma wyższy priorytet niż operatory logiczne.

Answer 1

Analiza tego kodu ze względu na sortowanie dzielone pomiędzy pierwszą funkcją wołającą rekurencję, rekurencją i zmiennymi globalnymi jest trudna.

Ale można zobaczyć od końca programu, kiedy vis.size() != nei.size().

vis[imie] jest ustawiane za każdym wejściem do topoSort, a to jest dokonywane dla wszystkich nei[imie] w pętli w main. Więc coś musi się dziać z tymi imieniami, które nie są wymienione jako pierwsze. Czyli wiadomo już, że vis.size() >= nei.size(). Może być więcej imion wymienionych z prawej strony, które są przetwarzane przez rekurencyjne wywołania topoSort.

Ale jakie to ma znaczenie w tym algorytmie, nie wiem, ponieważ nie rozważam algorytmu sortowania. Przypuszczam, że może chodzić o to, iż pewne imiona mogą nie mieć ustalonej nadrzędności a istnieć w sta. Ponieważ później w conFn sprawdzasz tylko obecność duplikatów, a nie braków. Te komentarze o grafie są mylące, ponieważ tam nie ma żadnego grafu, są inne struktury.