Условие
Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин $u$, $v$ и $w$ из того, что из $u$ в вершину $v$ ведет ребро и из вершины $v$ в вершину $w$ ведет ребро, следует, что из вершины $u$ в вершину $w$ ведет ребро.
Проверьте, что заданный ориентированный граф является транизитивным.
Входные данные
Входной файл содержит число $n (1 \leq n \leq 100)$ — число вершин в графе, и затем $n$ строк по $n$ чисел, каждое из которых равно $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 |
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String answer = "YES"; short[][] graph = new short [n][n]; for (int i = 0; i < n; i++) { for( int j = 0; j < n; j++) { graph[i][j] = sc.nextShort(); } } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if (graph[i][j] == 1){ for (int z = 0; z < n; z++){ if (graph[j][z] == 1 && graph[i][z] == 0) { answer = "NO"; break; } } } } } System.out.print(answer); } } |
Решение
Представим матрицу смежности графа в виде двумерного массива. Тогда, если $graph[i][j]=1$, то из вершины $i$ в вершину $j$ ведёт ребро. Проверяем с помощью циклов транзитивность графа, то есть если из вершины $i$ в вершину $j$ ведёт ребро и из вершины $j$ в вершину $z$, то граф транзитивен, если есть ребро $graph[i][z]$.