Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Дан ориентированный невзвешенный связный граф. Требуется определить, содержит ли он циклы.

Входные данные: Первая строка содержит одно натуральное число n — количество вершин (0 ≤ n ≤ 1 111).

Следующие n строк содержат матрицу смежности графа. Если в позиции (i, j) квадратной матрицы стоит единичка, то i-ый и j-ый ребра соединены ребрами, а если нолик, то не соединены. При этом ребро направленно из i-ого в j-ое ребро графа, и j-ое и i-ое ребро не соеденены ребрами.

Выходные данные: Первая строка должна содержать YES, если граф содержит цикл и NO — в противном случае.

Примеры

№	Входные данные	Выходные данные
1	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

Обход в глубину

✓ 68✗ 173700средняяВойти и решать

Negcycle. Отрицательный цикл#18440

Дан взвешенный ориентированный граф. Требуется определить, содержит ли он цикл отрицательного веса. Гарантируется, что все вершины графа достижимы из первой.

Входные данные:
Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно ( n ≤ 1 111, m ≤ 11 111).
Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя числами bi, ei и wi — номера концов ребра и его вес соответственно (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000). Обратите внимание, что в графе могут быть кратные ребра и петли.

Выходные данные:
Первая строка выходного файла должна содержать yes, если граф содержит цикл отрицательного веса и no — в противном случае.

Примеры

№	Входные данные	Выходные данные
1	4 4 2 1 -4 1 2 1 3 4 2 2 3 3	yes
2	4 6 2 1 4 1 2 1 3 4 2 2 3 3 1 1 2 1 2 2	no

Алгоритм Форда-Беллмана

✓ 70✗ 190600лёгкаяВойти и решать