Способы задания графа

20 задач

Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.

РейтингЛюбой до 800 800–1199 1200–1599 1600+Без рейтинга

СначалаПодходящие Новые Популярные Простые Сложные

Турнир#54188

Ориентированный граф называется турниром, если между любой парой его различных вершин существует ровно одно ребро. Для заданного списком ребер графа проверьте, является ли он турниром.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m ( 1 \leq m \leq n (n-1))\) – количество ребер. Затем следует m пар чисел – ребра графа.

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

Способы задания графа

✓ 58✗ 96700средняяВойти и решать

Полуполный граф#54187

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

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n-1))\) – количество ребер. Затем следует m пар чисел – ребра графа.

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

Способы задания графа

✓ 90✗ 234400лёгкаяВойти и решать

Полный граф#54183

Неориентированный граф с кратными рёбрами называется полным, если любая пара его различных вершин соединена хотя бы одним ребром. Для заданного списком ребер графа проверьте, является ли он полным.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m ( 1 \leq m \leq n (n-1)/2)\) – количество ребер. Затем следует m пар чисел – ребра графа.

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

Способы задания графа

✓ 69✗ 40500лёгкаяВойти и решать

Регулярный граф#54180

Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ли он регулярным.

Входные данные
Сначала вводятся числа n ( 1≤n≤100) – количество вершин в графе и \(m (0 \leq m \leq n (n - 1)/2)\) – количество ребер. Затем следует m пар чисел – ребра графа.

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

Способы задания графа

✓ 71✗ 68600лёгкаяВойти и решать

Истоки и стоки#54176

Напомним, что вершина ориентированного графа называется истоком, если в нее не входит ни одно ребро и стоком, если из нее не выходит ни одного ребра.

Ориентированный граф задан матрицей смежности. Найдите все вершины графа, которые являются истоками, и все его вершины, которые являются стоками.

Входные данные
Сначала вводится число n ( 1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные
Вначале выведите k – число истоков в графе и затем k чисел – номера вершин, которые являются истоками, в возрастающем порядке. Затем выведите информацию о стоках в том же порядке.

Способы задания графа

✓ 55✗ 34600лёгкаяВойти и решать

Полустепени вершин по спискам ребер#54171

Ориентированный граф задан списком ребер. Найдите степени всех вершин графа.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n-1))\) – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

Способы задания графа

✓ 47✗ 31700средняяВойти и решать

Полустепени вершин#54167

Ориентированный граф задан матрицей смежности. Найдите полустепени захода и полустепени исхода всех вершин графа.

Входные данные
Сначала вводится число n ( 1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Выходные данные
Выведите n пар чисел – для каждой вершины сначала выведите полустепень захода и затем полустепень исхода.

Способы задания графа

✓ 36✗ 20700средняяВойти и решать

Степени вершин по спискам ребер#54163

Неориентированный граф задан списком ребер. Найдите степени всех вершин графа.

Входные данные
Сначала вводятся числа n ( 1≤n≤100 ) – количество вершин в графе и \(m (1 \leq m \leq n (n - 1) / 2)\) – количество ребер. Затем следует m пар чисел – ребра графа.

Выходные данные
Выведите n чисел – степени вершин графа.

Способы задания графа

✓ 39✗ 14700средняяВойти и решать

Подсчет количества ребер ориентированного графа#54152

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

Входные данные
На вход программы поступает число n ( 1≤n≤100 ) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

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

Способы задания графа

✓ 33✗ 5700средняяВойти и решать

Подсчет количества ребер неориентированного графа#54149

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

Входные данные
На вход программы поступает число n ( 1≤n≤100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

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

Способы задания графа

✓ 29✗ 3700средняяВойти и решать

От списка ребер к матрице смежности, ориентированный вариант#49243

Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

Формат входных данных

На вход программы поступают числа n ( 1 ≤ n ≤ 100) - количество вершин в графе и m (1 ≤ m ≤ n(n-1)) – количество ребер. Затем следует m пар чисел – ребра графа.

Формат выходных данных

Выведите матрицу смежности заданного графа.

Способы задания графа

✓ 751✗ 193200лёгкаяВойти и решать

От матрицы смежности к списку ребер, ориентированный вариант#49242

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

Формат входных данных

На вход программы поступает число n (1 ≤ n ≤ 100) – количество вершин графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных
Выведите список ребер заданного графа в порядке возрастания номеров вершин.

Способы задания графа

✓ 695✗ 231300лёгкаяВойти и решать

Степени вершин#33471

Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

Формат входных данных
В первой строке вводится число n (1 ≤ n ≤ 100) – количество вершин в графе. Далее идет n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.

Формат выходных данных
Выведите n чисел – степени вершин графа (по одному числу в строке).

Способы задания графа

✓ 1 163✗ 272300лёгкаяВойти и решать

От списка ребер к матрице смежности, неориентированный вариант#33132

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.

Формат входных данных
В первой строке задаются числа n (\(1<=n<=100\)) – количество вершин в графе и m (\(1<=m<=n(n - 1)/2\)) – количество ребер. Далее следует m пар чисел – ребра графа (каждая пара чисел в отдельной строке).

Формат выходных данных
Выведите матрицу смежности заданного графа.

Способы задания графа

✓ 1 316✗ 863300лёгкаяВойти и решать

От матрицы смежности к списку ребер, неориентированный вариант#33131

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.

Формат входных данных
Входные данные включают число n (\( 1<=n<=100\)) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.

Формат выходных данных
Выведите список ребер заданного графа (в любом порядке).

Способы задания графа

✓ 1 100✗ 599300лёгкаяВойти и решать

Проверка на неориентированность#33130

По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – размер матрицы. Затем задается сама матрица - n строк по n чисел, каждое из которых равно 0 или 1.

Формат выходных данных
Выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае

Способы задания графа

✓ 1 193✗ 2 232400лёгкаяВойти и решать

Петли#33129

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.

Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – количество вершин графа. Затем задается матрица смежности - n строк по n чисел, каждое из которых равно 0 или 1.

Формат выходных данных
Выведите «YES», если граф содержит петли, и «NO» в противном случае.

Способы задания графа

✓ 1 303✗ 825300лёгкаяВойти и решать

Цветной дождь#22019

В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых - синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся.
Посчитать количество таких "плохих" мостов.

Формат входных данных
В первой строке записано N (\(0<N<=100\)) - число холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). В последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый.

Формат выходных данных
Вывести количество "плохих" мостов.

Способы задания графа

✓ 1 167✗ 751400лёгкаяВойти и решать

Светофорчики-1#22018

В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

Формат входных данных
В первой строке записано два числа N и M (\(0<N<=100\), \(0<=M<=N*(N-1)/2\) ). В следующих M строках записаны по два числа i и j (\(1<=i,j<=N\)), которые означают, что перекрестки i и j соединены тоннелем.

Формат выходных данных
Вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

Примечание
Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

Способы задания графа

✓ 1 277✗ 965400лёгкаяВойти и решать

Города и дороги#22017

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

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

Формат выходных данных
Вывести одно число - количество дорог на планете "Neptune".

Примечание

Все дороги двусторонние, то есть если есть дорога из города i в город j, то есть и дорога из города j в город i, и это та же самая дорога.

Способы задания графа

✓ 1 540✗ 1 017300лёгкаяВойти и решать