e-olimp 5079. Транзитивность ориентированного графа

Задача e-olimp 5079.

Условие

Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин [latex]u[/latex], [latex]v[/latex] и [latex]w[/latex] из того, что из [latex]u[/latex] в вершину [latex]v[/latex] ведет ребро и из вершины [latex]v[/latex] в вершину [latex]w[/latex] ведет ребро, следует, что из вершины [latex]u[/latex] в вершину [latex]w[/latex] ведет ребро.

Проверьте, что заданный ориентированный граф является транизитивным.

Входные данные

Входной файл содержит число [latex]n (1 \le n \le100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

Выходные данные

Выведите в выходной файл YES если граф является транзитивным и NO в противном случае.

Тесты

Входные данные Выходные данные
3
0 1 1
0 0 1
0 0 0
YES
3
0 1 1
1 0 0
0 1 0
NO

Код программы

Ссылка на засчитанное решение.
Для запроса на выполнение нажать здесь.

Решение

Представим матрицу смежности графа в виде двумерного массива. Тогда, если [latex]a[i][j] = 1[/latex], то из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро. Проверяем с помощью циклов транзитивность графа, то есть если из вершины [latex]i[/latex] в вершину [latex]j[/latex] ведёт ребро и из вершины [latex]j[/latex] в вершину [latex]z[/latex], то граф транзитивен, если есть ребро [latex]a[i][z][/latex].
 

Related Images:

Добавить комментарий