e-olymp 5071. Проверка на неориенитрованность

Задача. Проверка на неориенитрованность

Условие задачи
По заданной квадратной матрице $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

Код программы

Решение задачи

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: $a[i] = a[j]$. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

e-olymp 5082. Степени вершин

Задача

Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.

Входные данные

В первой строчке находится число $N (1 ≤ N ≤ 1000)$. В следующих $N$ строчках находится матрица смежности.

Выходные данные

Выведите $N$ чисел – степени всех вершин.

Тесты

Входные данные Выходные данные
2
0 1
1 0
1 1
3
0 1 0
1 0 1
0 1 0
1 2 1
5
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
6 1 6 1 6
5
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
3 3 2 1 1

Код программы

 

Решение задачи

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия $N$ раз, для каждой строки матрицы. Храним ответ в переменной counter , изначально $0$. По очереди считываем все ее элементы и, если текущий элемент равен $1$, то прибавялем степени $2$, если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — $2$. Затем выводим результат через пробел.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 2470. Проверка на неориентированность

Задача

По заданной квадратной матрице [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

Код программы

Решение задачи

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [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]

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 992. Города и дороги

Задача

В галактике «Milky Way» на планете «Neptune» есть n городов, некоторые из которых соединены дорогами. Император «Maximus» галактики «Milky Way» решил провести инвентаризацию дорог на планете «Neptune». Но, как оказалось, он не силен в математике, поэтому он просит Вас сосчитать количество дорог.

Вводные данные

В первой строке записано число $n$ $(0 \leq n \leq 100)$. В следующих $n$ строках записано по $n$ чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции $(i, j)$ квадратной матрицы стоит единичка, то $i$-ый и $j$-ый города соединены дорогами, а если нолик, то не соединены.

Выходные данные

Вывести одно число — количество дорог на планете «Neptune».

Тесты

Входные данные Выходные данные
$3$
$0$ $1$ $1$
$1$ $0$ $1$
$1$ $1$ $0$
$3$
$3$
$0$ $1$ $0$
$1$ $0$ $0$
$0$ $0$ $0$
$1$
$5$
$0$ $1$ $0$ $1$ $1$
$1$ $0$ $0$ $0$ $0$
$0$ $0$ $0$ $0$ $0$
$1$ $0$ $0$ $0$ $0$
$1$ $0$ $0$ $0$ $0$
$3$

Код программы(использование матрицы смежности)

Решение задачи(использование матрицы смежности)

Для решения задачи вводим матрицу смежности. Далее в цикле проходим верхнюю треугольную часть матрицы смежности и если попадается $1$, то увеличиваем число дорог на $1$. Выводим количество дорог. Задача решена.

Код программы(потоковая обработка)

Решение задачи(потоковая обработка)

Для решения задачи вводим числа пока они вводятся. Поскольку дороги идут с одного города в другой и наоборот, то их количество будет равно половине единичек в матрице смежности, то есть половине единичек входящих во входной поток. Cчитаем их количество и делим на $2$. Выводим количество дорог. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(матрица смежности)
Код решения на ideone.com(потоковая обработка)

e-olymp 977. Дерево?

Задача

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Определить, является ли этот граф деревом.

Входные данные

Первая строка содержит количество вершин графа $n \left (1 \leq n \leq 100 \right).$ Далее записана матрица смежности размером $n × n$, в которой $1$ обозначает наличие ребра, $0$ — его отсутствие. Матрица симметрична относительно главной диагонали.

Выходные данные

Выведите сообщение YES, если граф является деревом, и NO в противном случае.

Тесты

Входные данные Выходные данные
[latex]3 \\ 0 \ 1 \ 0 \\ 1 \ 0 \ 1 \\ 0 \ 1 \ 0[/latex] [latex]YES[/latex]
[latex]2 \\ 0 \ 1 \\ 1 \ 0[/latex] [latex]YES[/latex]
[latex]4 \\ 0 \ 0 \ 0 \ 1 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 1 \ 0 \ 0 \ 0[/latex] [latex]NO[/latex]
[latex]1 \\ 0[/latex] [latex]YES[/latex]

Код программы

Решение задачи

Считываем граф в ArrayList<ArrayList>. Далее выбираем любую вершину и запускаем из нее своего рода dfs. Заключается он в том, что мы идем к потомкам текущей вершины, попутно смотря были ли мы здесь. Если были, завершаем процесс, так как мы нашли цикл (граф, содержащий цикл, не является деревом). При этом мы не идем от потомка к предку. В конце проверяем обошли ли мы все вершины и не встречались ли нам циклы.

Ссылки

Условие задачи на e-olymp
Код решения

e-olymp 5080. Количество висячих вершин 1

Задача

Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна $1.$

Входные данные

В первой строке находится число $n$ $\left ( 1 \leq n \leq 1000 \right ).$ В следующих $n$ строках находится матрица смежности.

Выходные данные

Выведите количество висячих вершин в графе.

Тесты

Входные данные Выходные данные
$2 \\ 0 \ 1 \\ 1 \ 0$ $2$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 1 \ 0$ $0$
$4 \\ 1 \ 0 \ 0 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1$ $4$
$3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 0 \ 0$ $1$

Код программы

Решение

Введем обозначения: $gr$ – имя массива(матрицы смежности), $n$ – количество вершин, $cnt$ – счётчик.
Просматривая матрицу смежности, подсчитываем количество единиц, т.е количество инцидентных вершин данной вершине. Инцидентные вершины — вершины, которые соединены ребром. Степенью вершины называется количество рёбер, инцидентных этой вершине. Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице только одна единица, то вершина имеет степень 1 и является висячей.
Сперва предположим, что что граф не имеет висячих вершин, далее введём матрицу смежности, подсчитаем степень вершины и проверим, является ли вершина висячей. В ответе выводим количество висячих вершин в графе.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

e-olymp 5072. Подсчет количества ребер

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

Входные данные:

Входной файл содержит число [latex]n(1 \leq n \leq 100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — его матрицу смежности.

Выходные данные:

Выведите в выходной файл количество ребер заданного графа.

Тест

Значения Результат
1 3
0 1 1
1 0 1
0 1 1
6

Решение

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную  n типа int. Чтобы найти количество ребер в графе, вводим в двух циклах каждый элемент матрицы смежности и если значение больше нуля, то увеличиваем сумму.

e-olymp 974. Флойд-1

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Входные данные

В первой строке записано количество вершин графа n (1 ≤ [latex]n[/latex] ≤ 100). В следующих n строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

Выходные данные

Выведите [latex]n[/latex] строк по [latex]n[/latex] чисел — матрицу кратчайших расстояний между парами вершин. [latex]j[/latex]-ое число в [latex]i[/latex]-ой строке должно равняться весу кратчайшего пути из вершины [latex]i[/latex] в вершину [latex]j[/latex].

Алгоритм

(взято с Википедии)

Пусть вершины графа [latex]{\displaystyle G=(V,\;E),\;|V|=n}[/latex] пронумерованы от 1 до [latex] {\displaystyle n}[/latex] и введено обозначение [latex]{\displaystyle d_{ij}^{k}}[/latex] для длины кратчайшего пути от [latex] {\displaystyle i}[/latex] до [latex]{\displaystyle j}[/latex], который кроме самих вершин [latex] {\displaystyle i,\;j} [/latex] проходит только через вершины [latex]{\displaystyle 1\ldots k} [/latex]. Очевидно, что [latex]{\displaystyle d_{ij}^{0}} [/latex] — длина (вес) ребра [latex]{\displaystyle (i,\;j)}[/latex], если таковое существует (в противном случае его длина может быть обозначена как [latex]{\displaystyle \infty } [/latex] ).

Существует два варианта значения [latex] {\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)} d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)[/latex]:

Кратчайший путь между [latex]{\displaystyle i,\;j}[/latex] не проходит через вершину [latex] {\displaystyle k}[/latex], тогда [latex]{\displaystyle d_{ij}^{k}=d_{ij}^{k-1}}[/latex] Существует более короткий путь между [latex]{\displaystyle i,\;j}[/latex], проходящий через [latex]{\displaystyle k}[/latex], тогда он сначала идёт от [latex]{\displaystyle i} [/latex] до [latex] {\displaystyle k} [/latex], а потом от [latex] {\displaystyle k} [/latex] до [latex] {\displaystyle j} [/latex]. В этом случае, очевидно, [latex]{\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}[/latex]

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для [latex]{\displaystyle d_{ij}^{k}}[/latex] имеет вид:

[latex]{\displaystyle d_{ij}^{0}}[/latex] — длина ребра [latex] {\displaystyle (i,\;j);} (i,\;j);[/latex] [latex]{\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}[/latex]

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения [latex]{\displaystyle d_{ij}^{k},} [/latex], [latex]{\displaystyle \forall i,\;j}[/latex] для [latex] {\displaystyle k} [/latex] от 1 до [latex] {\displaystyle n} [/latex]. Полученные значения [latex] {\displaystyle d_{ij}^{n}}[/latex] являются длинами кратчайших путей между вершинами [latex]. {\displaystyle i,\;j.} [/latex].

Код

Условие на e-olymp.com
Решение на e-olymp.com
Код на ideone.com

e-olymp 5082. Degrees of vertices

Задача взята с сайта e-olymp.com.

Условие

Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.

Входные данные

В первой строчке находится число 1 \leq N \leq 1000. В следующих N строчках находится матрица смежности.

Выходные данные

Выведите N чисел – степени всех вершин.

Тесты :

Ввод Вывод
2
0 1
1 0
1 1
 3
0 1 0
1 0 1
0 1 0
 1 2 1
 3
0 1 0
1 1 1
0 1 0
1 4 1
 5
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
 6 1 6 1 6
 5
0 0 1 0 0
0 1 0 1 0
0 1 1 1 0
0 1 0 1 0
1 0 0 0 1
 1 3 4 3 3
 5
0 1 1 1 1
1 0 0 0 0
0 1 1 1 0
0 0 0 0 1
1 1 1 1 0
 4 1 4 1 4
 5
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
 3 3 2 1 1

Код на Java:

Алгоритм:

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия N раз, для каждой строки матрицы. Храним ответ в переменной counter, изначально 0. По очереди считываем все ее элементы и, если текущий элемент равен 1, то прибавляем степени 2, если элемент принадлежит главной диагонали (так как тогда это ребро является петлей, а при подсчете степени ребро-петля учитывается дважды), иначе прибавляем 1. Формируем строку-результат и выводим её.

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com