Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Алгоритмы на графах

Условие задачи  
ID 33226: Количество дорог
Количество дорог
Темы: Алгоритмы на графах   

Напишите программу, которая считает количество дорог в городе Новые Васюки. Схема дорог задана как матрица смежности графа. На некоторых дорогах введено одностороннее движение.
 
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему дорог.
 
Выходные данные
Программа должна вывести одно число – количество дорог в Новых Васюках. Дороги с двусторонним движением нужно считать только один раз.

Ввод Вывод
5
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
0 0 0 0 0
0 1 0 1 0
7

ID 33129: Петли
Петли
Темы: Алгоритмы на графах   

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.
 
Входные данные: На вход программы поступает число n ( 1<=n<=100) – количество вершин графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
 
Выходные данные: Выведите  «YES», если граф содержит петли, и «NO» в противном случае.
 
Входные данные Выходные данные
1
5
1 1 1 1 0 
1 0 1 1 1 
1 1 0 1 1 
1 1 1 1 1 
0 1 1 1 0 
YES

ID 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
5
0 1 0 0 0 
1 0 1 1 0 
0 1 0 0 0 
0 1 0 0 0 
0 0 0 0 0
3
 

ID 33227: Суммарная длина дорог
Суммарная длина дорог
Темы: Алгоритмы на графах   

Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.
 
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – длины дорог между каждой парой перекрёстков. Ноль означает, что дороги между этими перекрёстками нет.
 
Выходные данные
Программа должна вывести одно число – суммарную длину дорог. Дороги с двусторонним движением нужно считать только один раз.

Ввод Вывод
5
0 2 3 4 0
2 0 5 0 7
3 6 0 8 0
0 0 0 0 0
0 7 0 9 0
44

ID 22018: Светофорчики-1
Светофорчики-1
Темы: Алгоритмы на графах   

В подземелье 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
7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3
3 3 2 2 5 2 3
 

ID 33130: Проверка на неориентированность
Проверка на неориентированность
Темы: Алгоритмы на графах   

По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.
 
Входные данные: На вход программы поступает число n ( 1<=n<=100) – размер матрицы, а затем n строк по n чисел, каждое из которых равно 0 или 1, – сама матрица.
 
Выходные данные: Выведите  «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае.
 
Входные данные Выходные данные
1
5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 
YES

ID 33131: От матрицы смежности к списку ребер, неориентированный вариант
От матрицы смежности к списку ребер, неориентированный вариант
Темы: Алгоритмы на графах   

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
 
Входные данные: Входные данные включают число n ( 1<=n<=100) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.
 
Выходные данные: Выведите  список ребер заданного графа (в любом порядке).
 
Входные данные Выходные данные
1
5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 
1 3
2 3
2 5

ID 33132: От списка ребер к матрице смежности, неориентированный вариант
От списка ребер к матрице смежности, неориентированный вариант
Темы: Алгоритмы на графах   

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.
 
Входные данные: На вход программы поступают числа n ( 1<=n<=100) – количество вершин в графе и m ( 1<=m<=n(n - 1)/2) – количество ребер. Затем следует m пар чисел – ребра графа.
 
Выходные данные: Выведите матрицу смежности заданного графа.
 
Входные данные Выходные данные
1
5 3
1 3
2 3
2 5
0 0 1 0 0 
0 0 1 0 1 
1 1 0 0 0 
0 0 0 0 0 
0 1 0 0 0 

ID 22019: Цветной дождь
Цветной дождь
Темы: Алгоритмы на графах   

В Банановой республике очень много холмов, соединенных мостами. 
На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых -  синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся.
Посчитать количество таких "плохих" мостов.
 
Входные данные: В первой строке записано N (0<N<=100) - число холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). 
В последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый.
 
Выходные данные: Вывести количество "плохих" мостов. 
 
Примеры
Входные данные Выходные данные
1
7
0 1 0 0 0 1 1 
1 0 1 0 0 0 0 
0 1 0 0 1 1 0 
0 0 0 0 0 0 0 
0 0 1 0 0 1 0 
1 0 1 0 1 0 0 
1 0 0 0 0 0 0 
1 1 1 1 1 3 3
4