Задача. Проверка на неориенитрованность
Условие задачи
По заданной квадратной матрице $n\times n$ из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.
Входные данные
Входной файл содержит число $n(1\leq n\leq 100)$ — размер матрицы, и затем $n$ строк по $n$ чисел, каждое из которых равно $0$ или $1$ — саму матрицу.
Выходные данные
Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.
Тесты
| ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 3 0 1 1 1 0 1 1 1 0 |
YES |
| 3 0 1 0 1 0 1 1 1 0 |
NO |
| 3 0 1 0 1 1 1 0 1 0 |
NO |
| 4 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 |
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 30 31 32 33 34 35 36 37 38 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = n*n; int [] G = new int [k]; for (int i = 0; i < G.length; i++) { G[i] = in.nextInt(); } int j = 0, c = 0, s = 0; boolean f = true; for (int i = 0; i < k; i++) { if (G[i] != G[j]) { f=false; break; } if (c == n - 1) { c = 0; s++; j = s; } else { j = j + n; c++; } } for (int i = 0; i < k; i = i + n + 1) { if (G[i] != 0) { f = false; break; } } if (f) System.out.print("YES"); else System.out.print("NO"); } } |
Решение задачи
Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: $a[i] = a[j]$. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную
f типа
bool. Изначально
f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».