Описание

Ограничение по времени: 500 ms
Ограничение по памяти: 32 Mb

Ответы на вопросы

Задача: Поиск циклов в графе

Поиск циклов в графе
 
Дан ориентированный невзвешенный связный граф. Требуется определить, содержит ли он циклы.
 
Формат входных данных
Первая строка содержит одно натуральное число n — количество вершин (0 ≤ n ≤ 1 111).
Следующие n строк содержат матрицу смежности графа. Если в позиции (i, j) квадратной матрицы стоит единичка, то i-ый и j-ый ребра соединены ребрами, а если нолик, то не соединены. При этом ребро направленно из i-ого в j-ое ребро графа, и j-ое и i-ое ребро не соеденены ребрами.
 
Формат выходных данных
Первая строка выходного файла должна содержать YES, если граф содержит цикл и NO — в противном случае.

Пример ввода:
8
0 1 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0

Пример вывода:
YES


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: