Задача
По заданной квадратной матрице n×n из нулей и единиц определить, может ли она быть матрицей смежности простого неориентированного графа. Напомним, что простой граф не содержит петли и мультиребра.
Входные данные
В первой строке задано число (1⩽n⩽100). Затем идут n строк по n элементов в каждой — описание матрицы смежности.
Выходные данные
Вывести YES, если граф простой неориентированный, и NO в противном случае.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 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 |
Код программы
Решение задачи
Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: a[i][j]=a[j][i]. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия. Для этого воспользуемся обычными двумерными массивами. Затем проверим является ли граф простым. Если a[i][j]=1, то граф содержит петлю, следовательно простым не является. Затем проверим матрицу на симметричность, т. е. выполняется ли условие a[i][j]=a[j][i]. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, то это означает, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».