Znalazłem podobny do BFS-a algorytm, w którym nie musimy martwić się o spójność grafu - co powinno uprościć zadanie
https://en.wikipedia.org/wiki/Topological_sorting#Kahn’s_algorithm
Wydaje się być swojego rodzaju uogólnieniem BFS-a na skierowane grafy, które niekoniecznie są spójne