Задача 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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> using namespace std; int main() { int n; cin >> n; bool arr[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin >> arr[i][j]; } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { // если существует ориентированное ребро, соединяющее вершины i и j if(arr[i][j]) { for(int z = 0; z < n; z++) { // если из вершины j в вершину z ведёт ребро, но из i в z - нет, то граф нетранзитивен if(arr[j][z] && !arr[i][z]) { cout << "NO"; return 0; } } } } } cout << "YES"; return 0; } |
Ссылка на засчитанное решение.
Для запроса на выполнение нажать здесь.
Решение
Представим матрицу смежности графа в виде двумерного массива. Тогда, если [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].