|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 08-3. Цикл
| Имя входного файла | input.txt |
| Имя выходного файла | output.txt |
| Максимальное время работы на одном тесте: | 5 секунд |
Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.
Формат входных данных
Во входном файле в первой строке записано число
N (1 <= N <= 100) - количество вершин графа. В следующих N строках
находится по N чисел - матрица смежности графа.
Веса ребер не превышают по модулю 10000. Если ребра нет,
соответствующее значение равно 100000.
Формат выходных данных
В первой строке выходного файла выведите "YES",
если цикл существует, или "NO" в противном случае.
При наличии цикла выведите во второй строке количество
вершин в нем (считая одинаковые первую и последнюю)
и в третьей строке - вершины, входящие в этот цикл в порядке
обхода. Если циклов несколько - выведите любой.
Пример
| input.txt | output.txt |
2 0 -1 -1 0 |
YES 3 1 2 1 |