Задача
По заданной квадратной матрице [latex]n×n[/latex] из нулей и единиц определить, может ли она быть матрицей смежности простого неориентированного графа. Напомним, что простой граф не содержит петли и мультиребра.
Входные данные
В первой строке задано число [latex](1 \leqslant n \leqslant 100).[/latex] Затем идут [latex]n[/latex] строк по [latex]n[/latex] элементов в каждой — описание матрицы смежности.
Выходные данные
Вывести [latex]YES,[/latex] если граф простой неориентированный, и [latex]NO[/latex] в противном случае.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 0 1 1 1 0 1 1 1 0 |
YES |
| 2 | 3 0 1 1 1 0 1 0 1 0 |
NO |
| 3 | 3 0 1 0 1 1 1 0 1 0 |
NO |
| 4 | 4 1 1 1 1 1 0 1 1 1 1 0 1 |
NO |
| 5 | 4 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 |
YES |
Код программы
|
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 30 31 |
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Scanner in = new Scanner(System.in); int n = in.nextInt(); int a[][] = new int[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { a[i][j] = in.nextInt(); if ((i == j) && (a[i][j] == 1)) { System.out.print("NO"); return; } } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if (a[i][j] != a[j][i]) { System.out.print("NO"); return; } } } System.out.print("YES"); } } |
Решение задачи
Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j] = a[j][i].[/latex] Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия. Для этого воспользуемся обычными двумерными массивами. Затем проверим является ли граф простым. Если [latex]a[i][j] = 1,[/latex] то граф содержит петлю, следовательно простым не является. Затем проверим матрицу на симметричность, т. е. выполняется ли условие [latex]a[i][j] = a[j][i].[/latex] Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, то это означает, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится [latex]«NO».[/latex] Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим [latex]«YES».[/latex]