Задачи на графах

-= заготовка статьи =-
Общим для задач на графах является необходимость их как-то хранить в программе. Для хранения графа [latex] G \left( V, E \right), |V| = n, |E| = m [/latex] в разных случаях используют различные методы. Наиболее популярны из них:

Матрица смежности [latex] O \left( n^2 \right) [/latex]
Матрица инцидентности [latex] O \left( n \cdot m \right)[/latex]
списки рёбер [latex] O \left( m \right)[/latex]

Хорошая идея почитать про алгоритмы на графах здесь и посмотреть решения задач здесь.

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

Ваш браузер не поддерживает плавающие фреймы, посетите http://mist.mazurok.com

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

A1038. Дейкстра? Опубликовал 06/12/2017Калачьов Андрій Сергійович
Задача: Имеется n ...
AL15. Лабиринт Опубликовал 11/04/2016Сплошнов Кирилл
Условие Матрица размера определяет свободное место. В первой строке ...
e-olimp 4000. Обход в глубину Опубликовал 30/04/2015Ковальський Олександр Дмитрович
Задача e-olimp 4000 Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте ...
e-olimp 4650. Граф-Турнир Опубликовал 08/05/2015Іванов Вячеслав Володимирович
Граф-турнир. Постановка задачи Построить на n вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер. Алгоритм решения Условию удовлетворяет любая ...
e-olimp 4852. Кратчайшее расстояние Опубликовал 27/06/2016Аня Шохина
Задача Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа. Входные данные В первой строке содержатся два натуральных ...
e-olimp 4856. Кратчайший путь Опубликовал 24/04/2015Ілларіонова Марія Валеріївна
Задача e-olimp.com №4856. Ссылка на засчитанное решение. Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами. Входные данные Первая строка содержит ...
e-olimp 5074. Степени вершин по спискам ребер Опубликовал 02/05/2015Карташов Денис Геннадійович
Задача: Неориентированный граф задан списком ребер. Найдите степени всех вершин графа. Технические условия: Входные данные: Входной файл содержит числа (1 \leq n \leq ...
e-olimp 5075 Опубликовал 30/04/2015Денисова Ольга
Задача Ориентированный граф задан списком ребер. Найдите степени всех вершин графа. Входные данные. Входной файл содержит числа — число ...
e-olimp 5077. Полуполный граф Опубликовал 27/04/2015Бронфен-Бова Роман
Задача: Полуполный граф Решение ссылка на ideone, засчитанное решение на e-olymp Решение C++ #include<iostream> using namespace std; bool used; int main(){ int n, m; cin >> n >> ...
e-olimp 5078. Турнир Опубликовал 22/04/2015Ілларіонова Марія Валеріївна
Задача e-olimp.com №5078. Ссылка на засчитанное решение (C++). Ссылка на засчитанное решение (Java). Ориентированный граф называется турниром, если между любой парой его различных вершин ...
e-olimp 5079. Транзитивность ориентированного графа Опубликовал 11/05/2016Таня Корнилова
Задача e-olimp 5079. Условие Напомним, что ориентированный граф называется транзитивным, если для любых трех различных вершин из того, ...
e-olimp 5080. Количество висячих вершин 1 Опубликовал 29/04/2015Марченко Філіп Олександрович
Условие задачи Ссылка на засчитанное решение Ссылка на Ideone Код: C++ #include <iostream> #include <vector> using namespace std; int gr; // матрица смежности int n; //кол-во вершин //Просматривая матрицу смежности, ...
e-olymp 1108. Червячные дыры Опубликовал 06/06/2016Грешилов Константин
Условие: В 2163 году были обнаружены червячные дыры. Червячная дыра представляет собой тоннель сквозь пространство и время, соединяющий две звездные системы. ...
e-olymp 1390. Автогонки Опубликовал 18/12/2019Владимир Захаренко
Задача В городе $N$ в ближайшее время состоится этап чемпионата мира по автогонкам среди автомобилей класса Формула-0. Поскольку специальный автодром для ...
e-olymp 1453. Форд-Беллман Опубликовал 30/04/2016Молоканов Юрий
Условие Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). ...
e-olymp 1454. Лабиринт знаний Опубликовал 28/06/2015Ковальський Олександр Дмитрович
Задача В Летней Компьютерной Школе (ЛКШ) построили аттракцион «Лабиринт знаний». Лабиринт представляет собой n комнат, занумерованных от 1 до n, между ...
e-olymp 1455. Цикл Опубликовал 12/05/2016Катя Писова
Задача Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его. Входные данные Первая строка содержит количество ...
e-olymp 1821. Comparing Answers Опубликовал 23/06/2021Yezhkova
Problem In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there ...
e-olymp 1868. Функция Опубликовал 25/12/2017Иван Василевский
Условие задачи Вычислите функцию: f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если ...
e-olymp 1947. Конденсация графа Опубликовал 25/05/2017Валентина Андриеш
Условие задачи: Для заданного ориентированного графа найти количество ребер в его конденсации. Конденсацией орграфа G называют такой орграф G’, вершинами которого служат ...
e-olymp 1948. Топологическая сортировка Опубликовал 06/06/2016Грешилов Константин
Условие: Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины. Входные данные В первой строке содержатся количество вершин ≤ ...
e-olymp 209. Защита от копирования Опубликовал 29/05/2018Александра Рябова
Условие Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина ...
e-olymp 209. Защита от копирования Опубликовал 01/06/2019Владислав Бебик
Задача Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина ...
e-olymp 2267. Journey Опубликовал 03/06/2016Таран Таня
The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead ...
e-olymp 2270. Поиск цикла Опубликовал 02/12/2019Наташа Писаревская
Задача Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них. Входные данные В ...
e-olymp 2401. Обход в ширину Опубликовал 31/05/2016Андрей Яроцкий
Задача 2401 Условие Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой. Входные данные В первой строке содержится три натуральных ...
e-olymp 34. Слово спонсора Опубликовал 06/12/2019Артем Рогулин
Задача По завершению турнира «Новогодняя ночь» спонсор решил отправить $m$ призерам подарки по почте. Зная количество участников $n$ и время доставки ...
e-olymp 3835. Минимальный каркас Опубликовал 13/07/2021Yezhkova
Задача В связном графе найдите остовное дерево минимального веса. Входные данные Первая строка содержит два натуральных числа $n$ и $m$ $($$1 \leqslant n ...
e-olymp 4000. Обход в глубину Опубликовал 05/06/2018Кирилл Волков
Задача Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности ...
e-olymp 4002. Down with cheating! Опубликовал 10/04/2016Таран Таня
During the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark ...
e-olymp 4003. Топологическая сортировка Опубликовал 26/03/2016Сплошнов Кирилл
Задача взята отсюда. Условие Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать. Входные данные В первой строке содержатся два натуральных числа 1 \leq n ...
e-olymp 4050. Забавная игра Опубликовал 29/06/2015Зелінський Вячеслав Олександрович
Ссылка на задачу. Засчитанное решение. В одной стране есть несколько аэропортов, между некоторыми аэропортами есть рейсы. Можно перелететь из любого аэропорта в ...
e-olymp 45. Топливо Опубликовал 26/12/2018Кирилл Веремйов
Задача $N$ котелень одинаковой мощности соединены системой трубопроводов из $M$ труб для перекачки топлива. На $09:00$ утра оказалось, что фактические запасы ...
e-olymp 4850. Шайтан-машинка Опубликовал 17/06/2015Марченко Філіп Олександрович
Условие У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные ...
e-olymp 4852. Кратчайшее расстояние Опубликовал 23/05/2019Владимир Дроздин
Задача взята с сайта e-olymp. Задача Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа. Входные данные В первой ...
e-olymp 4853. Кратчайший путь Опубликовал 13/05/2015Осецимський Анатолій Вадимович
Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b. Условие задачи на e-olimp. Cсылка на пройденный тесты. Раз нам ...
e-olymp 4853. Кратчайший путь Опубликовал 26/06/2018Андрей Лисовой
Задача Задан неориентированный граф. Найдите кратчайший путь от вершины $a$ до вершины $b.$ Входные данные В первой строке находится два целых числа $n$ и ...
e-olymp 5071. Проверка на неориенитрованность Опубликовал 29/04/2016Кудымовская Вика
Задача. Проверка на неориенитрованность Условие задачи По заданной квадратной матрице из нулей и единиц определите, может ли данная матрица быть матрицей ...
e-olymp 5072. Подсчет количества ребер (ОГ) Опубликовал 28/05/2015Царев Николай Александрович
Задача Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе. Входные данные Входной файл содержит число n (1 ≤ n ≤ 100) — ...
e-olymp 5073. Проверка на наличие параллельных ребер (ОГ) Опубликовал 16/06/2015Байков Дмитро
Ориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра. Входные данные Входной файл содержит числа — число вершин в ...
e-olymp 5076. Регулярный граф Опубликовал 12/05/2015Калачьов Андрій Сергійович
Задача 5076: Неориентированный граф называется регулярным, если все его вершины имеют одинаковую степень. Для заданного списком ребер графа проверьте, является ...
e-olymp 5082. Степени вершин Опубликовал 19/04/2016Сплошнов Кирилл
Условие Задача взята с сайта e-olymp. Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень. Входные данные В первой строчке находится ...
e-olymp 5338. Полный граф — 2 Опубликовал 23/05/2019Инна Литвиненко
Задача Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. ...
e-olymp 610. Древняя рукопись Опубликовал 19/05/2018Мороз Дима
Задача В некоторой древней стране жили-были братья. Сколько их было, нам точно не известно, но в исторических источниках упоминается, что их точно ...
e-olymp 625. Расстояние между вершинами Опубликовал 17/06/2015Зелінський Вячеслав Олександрович
Задача с сайта e-olimp № 625. Ссылка на засчитанное решение. РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя ...
e-olymp 7213. Шашка на кубе Опубликовал 12/12/2020Максим Ливитчук
Условие Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше ...
e-olymp 7233. Путешествия в космосе Опубликовал 03/12/2020Євген Константинов
Задача Инфраструктура космической галактики состоит из прямых межпланетных маршрутов, каждый из которых связывает ровно две разные планеты. ...
e-olymp 88. Месть Ли Чака Опубликовал 04/02/2018Кирилл Волков
Задача “Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш ...
e-olymp 93. Truck driving Опубликовал 12/04/2018Александра Рябова
Task Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a ...
e-olymp 9414. Убить всех термитов Опубликовал 21/12/2019Андрей Метасов
Условие задачи На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с $n$ вершинами и $n ...
e-olymp 974. Флойд-1 Опубликовал 17/06/2015Зелінський Вячеслав Олександрович
974. Флойд-1 Ссылка на засчитанное решение. Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что ...
e-olymp 974. Флойд-1 Опубликовал 27/05/2016Радик Сиденко
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов ...
e-olymp 975 Опубликовал 26/06/2015Сіренко Валерія Сергіївна
Задача: Дан ориентированный взвешенный граф. Найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин. Входные ...
e-olymp 976. Флойд — существование Опубликовал 14/05/2015Осецимський Анатолій Вадимович
По некоторым причинам в статье рассматриваются две близкие задачи. Приведенный программный код содержит все необходимые функции, для решения обеих. Вставляя ...
e-olymp 978. Получи дерево Опубликовал 26/04/2016Павел Загинайло
Задача с сайта e-olymp.com. Условие Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево. Входные данные Первая ...
e-olymp 982. Связность Опубликовал 15/05/2016Женя Максимова
Задача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть ...