Dzień 10 - sortowanie topologiczne

Co za zbieg okoliczności. Wczoraj przygotowałam wpis na temat sortowania topologicznego (zauważyłam nowy moduł w Pythonie 3.9), a dzisiejsze zadanie właśnie takego przesortowania wierzchołków wymagało.

Przyznam się, że zrozumiałam to dopiero wtedy, gdy moje naiwne rozwiązanie, które sprawdziło się dla danych testowych, zupełnie zwisnęło na właściwych danych. Czekam, czekam, a tu nic.

W moim grafie, reprezentowanym jako dict, z wierzchołkiem (nominalną wartością zasilania przejściówki) związana była lista tych wierzchołków/przejściówek, do których można dany wierzchołek wpiąć. Adapter w fotelu nie może być nigdzie wpięty, więc ma pustą listę poprzedników. Sam stanowi poprzednik (a więc znajduje się na liście) pierwszego adaptera z mojego bagażu, który ma pasujący joltage. Adapter w sprzęcie nie będzie niczyim poprzednikiem (nie będzie się znajdował na liście poprzedników żadnego adaptera).

Jak już posortowałam moje przejściówki, mogłam zastosować programowanie dynamiczne. Dla każdego wierzchołka utrzymywałam liczbę ścieżek wychodzących z tego wierzchołka. Przechodziłam wierzchołki w kolejności odwrotnej do topologicznej (zaczęłam od portu 0, który był przy moim fotelu) i albo ustawiałam dla każdego z nich liczbę ścieżek wychodzących na 1 (jeśli nie miały poprzedników), albo zwiększałam tę liczbę o sumę - obliczonych juz wcześniej - ilości ścieżek wychodzących z każdego poprzednika.

Liczba ścieżek wychodzących z największego węzła (czyli przejściówki w moim sprzęcie) stanowiła rozwiązanie problemu.