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

[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

[Андрюха]

Олимпиадным задачам-олимпиадные методы!
Зададим сеть городов графом с ориентированными ребрами
Для каждой вершины выполним такие действия:
Занесем её в стек, пометим рассмотренной, рассмотрим все исходящие из нее ребра в неисследованные вершины, запишем их в конец стека, перейдем к следующей вершине в стеке и так пока не дойдем до конца
Если количество вершин в стеке равно общему-это вершина исток
Паралельно после рассмотрения каждой вершины будем формировать матрицу достижимостей вершин
Далее рассматриваем все вершины, проверяем их на достижимость из всех других и выводим вершины-стоки
Метод называется "Поиск в ширину на графе", в гугле пару миллионов ссылок найдешь)
Если надо-могу написать простейший код

[volvo]

Если надо-могу написать простейший код

Не надо... Во-первых, простейший код есть на форуме, а во вторых - олимпиадные задачи - очень скользкая тема, можно помочь, а не решить за кого-то...

[Michael_Rybak]

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

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

[Bard]

есть ли простейший код этой программы?

[Michael_Rybak]

Код описанного мной решения займет строчек эдак 200-400, и простейшим не будет.

А решение, предложенное Андрюхой, попробуй закодить сам, и приходи, когда будет что-то конкретное не получаться.