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!