Silnie spójne składowe

Question

Cześć,

Mam zadnie Drogi Rowerowe z XXV OI. https://szkopul.edu.pl/c/oboz10-14grupa2/problemset/problem/aKKSmtjWTtDOEHDqnmQ3-eAA/site/?key=statement

I w rozwiązaniu na stronie OI: https://www.youtube.com/watch?v=Oc1sTS_f5XA autor mówi, że najpierw dzielimy graf na silnie spójne składowe, potem taki graf składający się z silnie spójnych składowych sortujemy topologicznie i puszczamy na nim dynamika.

Ogólnie całe to rozwiązanie rozumiem(ostatnio nauczyłem się sortowania topologicznego), ale nie wiem jedynie jak podzielić graf na SCC. Coś wyczytałem w necie, że trzeba puścić dwa DFS-y, ale nie zbyt rozumiem o co chodziło w tym opisie.

Zna ktoś jakieś dobre wytłumaczenie tego, albo sam spróbuje to opisać?

Dzięki za pomoc!

Answer 1

Na cp-algorithms jest dobre wytłumaczenie z dowodem, dlaczego te dwa DFSy działają.