Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо.
Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до \(N\). После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине.
После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен.
Сначала на вход программы поступают числа \(N\) и \(M\) \((1 \leq N \leq 100, 1 \leq M \leq 5000)\) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел \(A\) и \(B\) по одной на строке \((1 \leq A, B \leq N)\), что означает, что, по мнению прапорщика, солдат \(A\) выше, чем \(B\). Не гарантируется, что все пары чисел во входных данных различны.
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите \(N\) чисел, разделенных пробелами, - одно из возможных построений.
| Ввод | Вывод |
|---|---|
2 2 1 2 2 1 |
No |
Задан ориентированный ациклический граф с \(n\) вершинами и \(m\) ребрами. Также задана перестановка вершин графа. Необходимо проверить, является ли данная перестановка топологической сортировкой.
В первой строке даны два числа \(n\) и \(m\) — количество вершин и ребер в графе соответственно (\(1 \leq n, m \leq 10^5\)). В следующих \(m\) строках заданы пары чисел \(u_i, v_i\), означающие, что в графе есть ребро из вершины \(u_i\) в вершину \(v_i\). В последней строке задана перестановка из \(n\) элементов.
Выведите "YES" (без кавычек), если данная перестановка является топологической сортировкой и "NO" в противном случае.
| Ввод | Вывод |
|---|---|
3 3 2 3 1 3 1 2 2 1 3 |
NO |
3 3 3 2 1 2 3 1 3 1 2 |
YES |
Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из \(n\) деталей, пронумерованных от 1 до \(n\), при этом деталь с номером \(i\) изготавливается за \(p_i\) секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.
Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.
Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдёт наименьшее время, за которое можно произвести деталь с номером 1.
Первая строка входного файла содержит число \(n\) (\(1\le n\le100000\)) — количество деталей двигателя. Вторая строка содержит \(n\) натуральных чисел \(p_1,p_2, \ldots,p_n\), определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит \(10^9\) секунд.
Каждая из последующих \(n\) строк входного файла описывает характеристики производства деталей. Здесь \(i\)-я строка содержит число деталей \(k_i\), которые требуются для производства детали с номером \(i\), а также их номера. В \(i\)-й строке нет повторяющихся номеров деталей. Сумма всех чисел \(k_i\) не превосходит 200000.
Известно, что не существует циклических зависимостей в производстве деталей.
В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число \(k\) деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел \(k\) чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.
| Ввод | Вывод |
|---|---|
3 100 200 300 1 2 0 2 2 1 |
300 2 2 1 |
2 2 3 1 2 0 |
5 2 2 1 |
Дан ориентированный граф. Проверить, является ли он сильно-связным.
В первой строке дано число \(n\) \((1 \leq n \leq 1000)\) — количество вершин графа. Далее в \(n\) строках дана матрица смежности этого графа. В графе могут быть петли.
Выведите «YES», если граф сильно связен, и «NO», если нет.
| Ввод | Вывод |
|---|---|
2 0 1 1 0 |
YES |
4 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 |
NO |
Вам задан ориентированный граф с \(N\) вершинами и \(M\) ребрами (\(1\le N\le 20 000\), \(1\le M\le 200 000\)). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.
Граф задан во входном файле следующим образом: первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк содержит описание ребра — два целых числа из диапазона от \(1\) до \(N\) — номера начала и конца ребра.
На первой строке выведите число \(K\) — количество компонент сильной связности в заданном графе. На следующей строке выведите \(N\) чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.
| Ввод | Вывод |
|---|---|
10 19 1 4 7 8 5 10 8 9 9 6 2 6 6 2 3 8 9 2 7 2 9 7 4 5 3 6 7 3 6 7 10 8 10 1 2 9 2 7 |
2 1 2 2 1 1 2 2 2 2 1 |
У компании BigData Inc. есть n дата-центров, пронумерованных от \(1\) до \(n\), расположенных по всему миру. В этих дата-центрах хранятся данные клиентов компании (как можно догадаться из названия — большие данные!)
Основой предлагаемых компанией BigData Inc. услуг является гарантия возможности работы с пользовательскими данными даже при условии выхода какого-либо из дата-центров компании из доступности. Подобная гарантия достигается путём использования двойной репликации данных. Двойная репликация — это подход, при котором любые данные хранятся в двух идентичных копиях в двух различных дата-центрах.
Про каждого из m клиентов компании известны номера двух различных дата-центров \(c_{i,1}\) и \(c_{i,2}\) , в которых хранятся его данные.
Для поддержания работоспособности дата-центра и безопасности данных программное обеспечение каждого дата-центра требует регулярного обновления. Релизный цикл в компании BigData Inc. составляет один день, то есть новая версия программного обеспечения выкладывается на каждый компьютер дата-центра каждый день.
Обновление дата-центра, состоящего из множества компьютеров, является сложной и длительной задачей, поэтому для каждого дата-центра выделен временной интервал длиной в час, в течение которого компьютеры дата-центра обновляются и, как следствие, могут быть недоступны. Будем считать, что в сутках h часов. Таким образом, для каждого дата-центра зафиксировано целое число \(u_j\) \(( 0 \leq u_j \leq h - 1)\), обозначающее номер часа в сутках, в течение которого \(j\)-й дата-центр недоступен в связи с плановым обновлением.
Из всего вышесказанного следует, что для любого клиента должны выполняться условия \(u_{c_{i,1}} \neq u_{c_{i,2}}\), так как иначе во время одновременного обновления обоих дата-центров, компания будет не в состоянии обеспечить клиенту доступ к его данным.
В связи с переводом часов в разных странах и городах мира, время обновления в некоторых дата-центрах может сдвинуться на один час вперёд. Для подготовки к непредвиденным ситуациям руководство компании хочет провести учения, в ходе которых будет выбрано некоторое непустое подмножество дата-центров, и время обновления каждого из них будет сдвинуто на один час позже внутри суток (то есть, если \(u_j = h - 1\), то новым часом обновления будет \(0\) , иначе новым часом обновления станет \(u_j + 1\)). При этом учения не должны нарушать гарантии доступности, то есть, после смены графика обновления должно по-прежнему выполняться условие, что данные любого клиента доступны хотя бы в одном экземпляре в любой час.
Учения — полезное мероприятие, но трудоёмкое и затратное, поэтому руководство компании обратилось к вам за помощью в определении минимального по размеру непустого подходящего подмножества дата-центров, чтобы провести учения только на этом подмножестве.
В первой строке находятся три целых числа \(n, m, h\) \((2 \leq n \leq 100 000 , 1 \leq m \leq 100 000 , 2 \leq h \leq 100 000)\) — число дата-центров компании, число клиентов компании и количество часов в сутках.
Во второй строке вам даны \(n\) чисел \(u_1 , u_2 , \ldots, u_n\) \(( 0 \leq u_j \lt h)\), \(j\)-е из которых задаёт номер часа, в который происходит плановое обновление программного обеспечения на компьютерах дата-центра \(j\) .
Далее в \(m\) строках находятся пары чисел \(c_{i,1}\) и \(c_{i,2}\) \((1 \leq c_{i,1} , c_{i,2} \leq n , c_{i , 1} \neq c_{i,2} )\), задающие номера дата-центров, на которых находятся данные клиента \(i\).
Гарантируется, что при заданном расписании обновлений в дата-центрах любому клиенту в любой момент доступна хотя бы одна копия его данных.
В первой строке выведите минимальное количество дата-центров \(k\) \(( 1 \leq k \leq n )\), которые должны затронуть учения, чтобы не потерять гарантию доступности. Во второй строке выведите k различных целых чисел — номера кластеров \(x_1 , x_2 , \ldots, x_k\) \(( 1 \leq x_i \leq n )\), на которых в рамках учений обновления станут проводиться на час позже. Номера кластеров можно выводить в любом порядке.
Если возможных ответов несколько, разрешается вывести любой из них. Гарантируется, что хотя бы один ответ, удовлетворяющий условиям задачи, существует.
| Ввод | Вывод |
|---|---|
3 3 5 4 4 0 1 3 3 2 3 1 |
1 3 |
4 5 4 2 1 0 3 4 3 3 2 1 2 1 4 1 3 |
4 1 2 3 4 |
В Якутске \(n\) домов. Некоторые из них соединены дорогами с односторонним движением.
В последнее время в Якутске участились случаи пожаров. В связи с этим жители решили построить в городе несколько пожарных станций. Но возникла проблема: едущая по вызову пожарная машина, конечно, может игнорировать направление движения текущей дороги, однако возвращающаяся с задания машина обязана следовать правилам дорожного движения (жители Якутска свято чтут эти правила!).
Ясно, что, где бы ни оказалась пожарная машина, у нее должна быть возможность вернуться на ту пожарную станцию, с которой выехала. Но строительство станций стоит больших денег, поэтому на совете города было решено построить минимальное количество станций таким образом, чтобы это условие выполнялось. Кроме того, для экономии было решено строить станции в виде пристроек к уже существующим домам.
Ваша задача — написать программу, рассчитывающую оптимальное положение станций.
В первой строке входного файла задано число \(n\) (\(1 \le n \le 3\,000\)). Во второй строке записано количество дорог \(m\) (\(1 \le m \le 100\,000\)). Далее следует описание дорог в формате \(a_i\) \(b_i\), означающее, что по \(i\)-й дороге разрешается движение автотранспорта от дома \(a_i\) к дому \(b_i\) (\(1 \le a_i, b_i \le n\)).
В первой строке выведите минимальное количество пожарных станций \(K\), которые необходимо построить. Во второй строке выведите \(K\) чисел в произвольном порядке — дома, к которым необходимо пристроить станции. Если оптимальных решений несколько, выведите любое.
| Ввод | Вывод |
|---|---|
5 7 1 2 2 3 3 1 2 1 2 3 3 4 2 5 |
2 5 4 |
2 1 1 2 |
1 2 |