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

82 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Вычисление простого выражения#44997

Напишите программу, которая вычисляет значение арифметического выражения, записанного в виде символьной строки. В выражении используются только целые числа и знаки арифметических операций (+-*/). Результат операции деления – целое число.

 

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

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

 

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

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

 
Примеры
№ Входные данные Выходные данные
1 
125-6-73/5*8
 
7
Деревья
✓ 26✗ 19500лёгкаяВойти и решать
Ветки дерева#44774

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


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

Вводится последовательность целых чисел,оканчивающаяся нулем. Построить по ней дерево.


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

Выведите список требуемых вершин.

 

Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
2
9
Двоичное дерево поискаДеревья
✓ 18✗ 17700средняяВойти и решать
Обход дерева#44773

Выведите все элементы полученного дерева в порядке возрастания.


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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. По данной последовательности требуется построить дерево.


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

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
1
2
3
4
5
6
7
8
9
Двоичное дерево поискаДеревья
✓ 27✗ 30600лёгкаяВойти и решать
Второй максимум в дереве#44772

Выведите второй по величине элемент в построенном дереве. Гарантируется, что такой найдется.


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

Дана последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.


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

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
8
Двоичное дерево поискаДеревья
✓ 19✗ 45700средняяВойти и решать
Сбалансированность#44649
Дерево называется сбалансированным, если для любой его вершины высота левого и правого поддерева для этой вершины различаются не более чем на 1.

Входные данные
Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте дерево, соответствующее данной последовательности.

Выходные данные
Определите, является ли дерево сбалансированным, выведите слово YES или NO.
 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
YES
Двоичное дерево поискаДеревья
✓ 20✗ 33700средняяВойти и решать
Выведи развилки#44648

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


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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит. Постройте по этой последовательности дерево.


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

Выведите ответ задачи.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
3
5
7
Двоичное дерево поискаДеревья
✓ 18✗ 16700средняяВойти и решать
Выведи листья#44647

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


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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.


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

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0

1
4
6
8
Двоичное дерево поискаДеревья
✓ 15✗ 10700средняяВойти и решать
Количество элементов в дереве#44646

Подсчитайте количество элементов в получившемся дереве и выведите это количество.


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

Вводится последовательность целых чисел, оканчивающаяся нулем. Сам ноль в последовательность не входит.


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

Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
9
Двоичное дерево поискаДеревья
✓ 33✗ 20500лёгкаяВойти и решать
Высота дерева#44645

Реализуйте бинарное дерево поиска для целых чисел. Программа получает на вход последовательность целых чисел и строит из них дерево. Элементы в деревья добавляются в соответствии с результатом поиска их места. Если элемент уже существует в дереве, добавлять его не надо. Балансировка дерева не производится.


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

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


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

Выведите единственное число – высоту получившегося дерева.

Пример соответствует следующему дереву:

 
Примеры
№ Входные данные Выходные данные
1 
7 3 2 1 9 5 4 6 8 0
 
4
Двоичное дерево поискаДеревья
✓ 30✗ 34500лёгкаяВойти и решать
Странный сон Константина#39670
Однажды Константин, поучаствовав в очередной, уже 13-ой по счету международной олимпиаде, возвращался на поезде домой. Он как всегда сидел и размышлял о смысле жизни, попутно решая задачи по программированию. Через некоторое время Константин задремал, но вот беда, для того, чтобы проснуться, он должен решить всплывшую у него в голове задачу, не дающую ему покоя!

В этот раз Константину приснилось дерево, изначально состоящее всего из одной вершины с номером 1. В поставленной им задаче к дереву постепенно добавлялись новые вершины. В i-ую секунду в дерево добавлялась вершина с номером i+1, которая подвешивалась в качестве сына к вершине pi, а на ребре между вершинами i+1 и pi записывалась буква ci.

Каждому пути из корня дерева до вершины v соответствует некоторая строка, получающаяся путем выписывания символов, записанных на ребрах текущего пути в порядке следования от корня к вершине v. Перед Константином стояла нелегкая на первый взгляд задача - после каждого добавления новой вершины посчитать количество уникальных строк, начинающихся в корне дерева (вершине с номером 1), и заканчивающихся в какой-либо другой вершине. 

В своем сне Константин вовсе не гений, поэтому решить эту задачу сам он не в силах. Помогите Константину решить задачу и тем самым проснуться.

Входные данные:
В первой строке записано число n - количество запросов на добавление новой вершины в дерево (1 <= n <= 300000).
В следующих n строках описаны запросы добавления вершин. i-ый запрос описывается параметрами pi (1 <= pi <= i) и ci, которые означают, что добавленная вершина с номером i+1 подвешивается к вершине с номером pi в качестве потомка, а на полученном ребре записывается символ ci - строчная буква латинского алфавита.

Выходные данные:
Выведите n строк. В i-ой строке выведите ответ на задачу Константина после добавления i+1-ой вершины.

Примеры:
 
Входные данные Выходные данные
2
1 b
2 p		 1
2
3
1 o
1 o
2 j		 1
1
2
БорДеревьяХеш
✓ 59✗ 360500лёгкаяВойти и решать
BFS: Начало (Python)#38792
Некоторые деревни соединены между собой дорогами, которые можно представить в виде неориентированного графа. Вершины данного графа - это деревни, а ребра - дороги между деревнями (граф может содержать циклы). Известно, что в деревне S основана артель коробейников. Каждое утро, чтобы продать свою мелкую галантерею, коробейники выходят в деревни, которые еще не посетили, и в которые есть дорога из текущей. Артель коробейников всегда делится на группы так, чтобы они могли за один день обойти все деревни, которые имеют дороги из текущей.
За сколько дней коробейники посетят все деревни?
Напишите функцию \(bfs()\), которая будет возвращать ответ на задачу.


Входные данные
В первой строке вводятся 3 целых числа n, m, s (\(1 <= n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - количество деревень, количество дорог между ними и номер деревни, в которой основана артель коробейников. В следующих m строках содержится по 2 числа u, v(\(1 <= u, v <= n\)) - номера двух деревень, между которыми есть дорога. Индексация деревень ведется с 1.

Выходные данные
Выведите одно число - за сколько дней коробейники посетят все деревни.
 
 
Примеры
№ Входные данные Выходные данные
1 6 7 1
1 2
1 5
2 3
5 4
3 4
3 6
4 6		 4
Обход в ширину
✓ 727✗ 3 207600лёгкаяВойти и решать
Площадь комнаты#38638
Требуется вычислить площадь комнаты в квадратном лабиринте.

Входные данные
В первой строке  вводится число N – размер лабиринта (3 <= N <= 10). В следующих N строках задан лабиринт (‘.’ – пустая клетка, ‘*’ – стенка). И наконец, последняя строка содержит  два числа – номер строки и столбца клетки, находящейся в комнате, площадь которой необходимо вычислить. Гарантируется, что эта клетка пустая и что лабиринт окружен стенками со всех сторон.

Выходные данные
Требуется вывести единственное число – количество пустых клеток в данной комнате.

 
Примеры
№ Входные данные Выходные данные
1 
5
*****
**..*
*.*.*
*..**
*****
2 4
 3
Обход в глубинуРекурсия
✓ 59✗ 108700средняяВойти и решать
Грядки*#33513
Прямоугольный садовый участок шириной N и длиной M метров разбит на квадраты со стороной 1 метр. На этом участке вскопаны грядки. Грядкой называется совокупность квадратов, удовлетворяющая таким условиям:

* из любого квадрата этой грядки можно попасть в любой другой квадрат этой же грядки, последовательно переходя по грядке из квадрата в квадрат через их общую сторону;
* никакие две грядки не пересекаются и не касаются друг друга ни по вертикальной, ни по горизонтальной сторонам квадратов (касание грядок углами квадратов допускается).
Подсчитайте количество грядок на садовом участке.

Входные данные
В первой строке находятся числа N и M через пробел, далее идут N строк по M символов. Символ # обозначает территорию грядки, точка соответствует незанятой территории. Других символов в исходном файле нет. 1 ≤ N, M ≤ 200.

Выходные данные
Вывести одно число - количество грядок на садовом участке.


Примеры
№ Входные данные Выходные данные
1 5 10 
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
 5
Обход в глубину
✓ 313✗ 422700средняяВойти и решать
Степени вершин#33471
Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

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

Формат выходных данных
Выведите n чисел – степени вершин графа (по одному числу в строке). 
Способы задания графа
✓ 1 152✗ 269300лёгкаяВойти и решать
Обход графа. Компонента связности#33465
Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин, лежащих в одной компоненте связности с данной вершиной (считая эту вершину).

Входные данные: В первой строке входных данных содержатся два числа: N и S (1 ≤ N ≤ 100; 1 ≤ S ≤ N), где N – количество вершин графа, а S – заданная вершина. В следующих N строках записано по N чисел – матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами, а 1 – его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные: Выведите одно целое число – искомое количество вершин.

Примеры
№ Входные данные Выходные данные
1 3 1
0 1 1
1 0 0
1 0 0		 3
Обход в глубину
✓ 1 041✗ 1 237400лёгкаяВойти и решать
Алгоритм Дейкстры за O(M logN)#33460

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

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

В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.

Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.

Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.
 

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

Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).
 

Алгоритм Дейкстры
✓ 161✗ 267700средняяВойти и решать
Цепочка слов#33313
Цепочкой слов длины n назовем последовательность слов w1, w2, ..., wn такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова wi + 1.
 
Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.
 
Задано множество слов S = {s1, s2, ..., sm}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.
 
Входные данные
Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.
 
Все слова не пусты, имеют длину, не превосходящую 255 символов, и состоят только из строчных букв латинского алфавита.
 
Выходные данные
В выходной файл выведите ответ на задачу.
 
Ввод Вывод
3
a
ab
abc
 3
5
a
ab
bc
bcd
add
 2
БорОбход в глубину
✓ 16✗ 46700средняяВойти и решать
Один конь#33251
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?
 
Формат входных данных
На вход программы поступает пять чисел: N, x1, y1, x2, y2 (\(5 <= N <= 20\), \(1 <= x_1,\ y_1,\ x_2,\ y_2 <= N\)). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).
 
Формат входных данных
Выведите единственное число K - наименьшее необходимое число ходов коня. 
Обход в ширину
✓ 589✗ 826600лёгкаяВойти и решать
Суммарная длина дорог#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

Алгоритмы на графах
✓ 457✗ 349500лёгкаяВойти и решать
Количество дорог#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

Алгоритмы на графах
✓ 434✗ 310500лёгкаяВойти и решать
Поделиться
Класснуть