Истоки и стоки, Олимпиадная задача Опции

[Bard]

Пусть нам задана карта односторонних дорог между городами.Город из которого можно добраться до всех других городов, называеться исток.Город в который можно добраться из всех других городов, называеться сток.Требуеться найти все стоки и истоки.

Заданные

N:число городов;
K:число дорог;
i и j:тоесть эта дорога соединяет i-й город с j-м.

Пример

Input.txt
6
10
2-1
2-4
4-1
4-2
4-3
1-3
3-5
5-3
3-6
6-3

Output.txt

stoki 3 5 6
istoki 2 4

[Michael_Rybak]

Задачу можно решить за O(n log n + k). Сначала выделяем сильно связные компоненты. Сворачиваем каждую компоненту в точку. Получаем ациклический граф. В ациклическом графе исток может быть только один (очевидно). Проходим по всем вершинам, ищем любую вершину А, в которую не входит ни одно ребро. Если исток вообще есть, то А и будет исток. Проверяем, исток ли это, запустив поиск в ширину. Если А не исток, то истоков в исходном графе нет. Если А исток, то в исходном графе истоками будут все вершины, входящие в сильно связную компоненту, которая свернулась в А.

Теперь меняем направления ребер и делаем то же самое - в результате находим стоки.