Задача. Проверка на неориенитрованность
Условие задачи
По заданной квадратной матрице [latex]n\times n[/latex] из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.
Входные данные
Входной файл содержит число [latex]n(1\leq n\leq 100)[/latex] — размер матрицы, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — саму матрицу.
Выходные данные
Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.
Также условие задачи можно посмотреть здесь.
Тестирование
| № | Входные данные | Выходные данные |
| 1. | 3 0 1 1 1 0 1 1 1 0 |
YES |
| 2. | 3 0 1 0 1 0 1 1 1 0 |
NO |
| 3. | 3 0 1 0 1 1 1 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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> G(n*n); for (int i = 0; i < G.size(); i++) { cin >> G[i]; } int j = 0, c = 0, s = 0; /*с - счетчик циклов, сигнализирует о завершении текущего цикла сравнения элементов i строки и j столбца; j - служит индексом для элементов столбца; s - счетчик столбцов, служит для задания нового начального значения индексу j при переходе к следующему циклу сравнения элементов i строки и j столбца;*/ bool f = true; for (int i = 0; i < n*n; i++)//задаем цикл по всему массиву { if (G[i] != G[j]) { f=false; break; } if (c == n - 1) { c = 0; s++; j = s; } /*если уже сравнили n-1 строку и столбец, обнуляем c, увеличиваем s и присваиваем его как новое начальное значение для индекса элементов столбца j*/ else { j = j + n;//на каждом шаге устанавливаем индекс для элемента столбца c++; } } for (int i = 0; i < n*n; i = i + n + 1) /*цикл для определения равенства нулю элементов главной диагонали - индекс увеличивается на n+1 на каждом шаге*/ { if (G[i] != 0) { f = false; break; } } if (f) cout << "YES"; else cout << "NO"; return 0; } |
Алгоритм решения
Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j]=a[j][i][/latex]. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную
f типа
bool. Изначально
f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».
Подробнее о графах и матрице смежности можно прочесть, используя следующие интернет-ресурсы:
Для запроса на выполнение следует перейти по ссылке.
Ссылка на засчитанное решение на e-olymp.com.
Мне кажется, что с обычными двумерными массивами все выглядело бы проще. Просто для элементов верхнего треугольника проверяем выполнение равенства a[i][j] == a[j][i].