Сложные задачи на поиск в глубину

Теория вся есть в том же тексте про поиск в глубину (ссылка выше на уровне 3), только теперь вам уже надо знать тут вообще всё.

Еще можете посмотреть на e-maxx, в частности, там есть простое доказательство алгоритма построения сильносвязных компонент.