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


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Ася и котята

Система непересекающихся множеств

Ася очень любит животных. Недавно она приобрела n котят, дала им числовые идентификаторы от 1 до n и поселила в вольере. Вольер представляет собой ряд из n ячеек, также пронумерованных от 1 до n. Cоседние ячейки разделены сетчатыми перегородками, всего в вольере n−1 перегородок. Изначально в каждой ячейке поселился ровно один котёнок с некоторым номером.

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

В i-й день Ася делала следующее.

Обращала внимание, что какие-то котята xi и yi, в i-й день живущие в соседних ячейках, хотят играть.
Удаляла перегородку между этими ячейками, превращая их в одну, в которой оказывались все котята из двух прежних ячеек.
Поскольку Ася не возвращала перегородки, через n−1 день вольер стал единой ячейкой, в которой обитали все котята. Будучи очень педантичной, Ася записывала в специальный журнал идентификаторы котят xi  и yi  для каждого из n−1 дней.

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

Входные данные
В первой строке задано целое число n (\(2 \leq n \leq 150000\)) — количество котят.

В следующих n−1 строках заданы пары целых чисел xi , yi  ( \(1 \leq x_i, y_i, \leq n,x_i \neq y_i\) ) — идентификаторы котят, между ячейками которых была удалена перегородка в день i. Гарантируется, что котята xi  и yi  не находятся в одной ячейке по итогам предыдущих объединений ячеек.

Выходные данные
Выведите n различных целых чисел pi (\(1 \leq p_i \leq n\)), где pi — идентификатор котёнка, который изначально жил в ячейке с номером i. Если возможных вариантов ответа несколько, выведите любой из них.

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

 

Ввод Вывод
5
1 4
2 5
3 1
4 5
3 1 4 2 5

Вес компоненты

Система непересекающихся множеств

В неориентированный взвешанный граф добавляют ребра. Напишите программу, которая в некоторые моменты находит сумму весов ребер в компоненте связности.
 
Входные данные
В первой строке записано два числа n и m (1≤n,m≤106) - количество вершин в графе и количество производимых добавлений и запросов. Далее следует m строк с описанием добавления или запроса. Каждая строка состоит из двух или четырех чисел. Первое из чисел обозначает код операции. Если первое число 1, то за ним следует еще три числа x, y, w. Это означает, что в граф добавляется ребро из вершины x в вершину y веса w. (1≤x<y≤n, 1≤w≤103). Кратные ребра допустимы. Если первое число 2, то за ним следует ровно одно число x. Это означает, что необходимо ответить на вопрос, какова сумма ребер в компоненте связности, которой принадлежит вершина x (1≤x≤n).
 
Выходные данные
Для каждой операции с кодом 2 выведите ответ на поставленную задачу. Ответ на каждый запрос выводите на отдельной строке.

Ввод Вывод
6 10
2 1
1 1 2 1
2 1
1 2 4 2
2 1
1 1 4 3
2 1
1 3 5 3
2 5
2 6
0
1
3
6
3
0
https://informatics.msk.ru/mod/statements/view3.php?id=1089&chapterid=1376#

Остовное дерево

Система непересекающихся множеств

Требуется найти в связном графе остовное дерево минимально веса.
 
Входные данные
Первая строка входного файла содержит два натуральных числа n и m - количество вершин и ребер графа соответственно (1≤n≤20000, 0≤m≤100000). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi - номера концов ребра и его вес соответственно (1≤bi,ei≤n, 0≤wi≤100000).
 
Граф является связным.
 
Выходные данные
Выведите единственное целое число - вес минимального остовного дерева.

Ввод Вывод
4 4
1 2 1
2 3 2
3 4 5
4 1 4
7

https://informatics.msk.ru/mod/statements/view3.php?id=1089&chapterid=1377#1

Минимальное остовное дерево c с данным ребром

Система непересекающихся множеств

Требуется найти в связном графе остовное дерево минимального веса в котором есть данное ребро.
 
Формат файла входных данных:
 
Первая строка входного файла содержит два натуральных числа N, M - количество вершин и ребер графа соответственно. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei, Wi номера концов ребра и его вес соответственно (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). В последней строке вводится данное ребро B, E, W.
 
Формат файла выходных данных:
 
Единственная строка выходного файла должна содержать одно натуральное число - вес минимального остовного дерева c данным ребром. 
 
Ввод:
 
4 4
1 2 1
2 3 2
3 4 5
4 1 4
1 4 7
 
Вывод:
7

Яблоки

Система непересекающихся множеств

У Даши есть n друзей, у каждого ai яблок. Все друзья образуют непересекающиеся компании. В любой момент времени две компании могут объединиться. Даша тщательно запомнила все действия друзей. Теперь ей интересно узнать, сколько яблок было в каждой новообразовавшейся компании. Изначально все друзья тусят отдельно, т.е. нет компании, где больше одного человека. У Даши нет яблок и она не принимает участия в объединениях.

Входные данные:
В первой строке - целые числа n и k ( 2 <= n <= 300000, 0 <= k <= n - 1 ) - количество друзей Даши и количество событий. Во второй строке n чисел - ai (0 <= ai <= 10^9) - количество яблок у i-того друга Даши. В следующих k строках по два числа u, v ( 1 <= u, v <= n). Событие (u, v) означает, что компания с u-тым другом Даши присоединилась к компании с v-тым другом. 

Выходные данные:
На каждый из k запросов выведите количество яблок в новой компании.

Ввод Вывод
3 2
1 2 3
1 2
1 3
3
6
2 1
999999999 0
1 2
999999999

(с) Ибрахим Ахмад, 2018

Острова

Система непересекающихся множеств

Одно разбросанное на островах Океании государство решило создать сеть автомобильных дорог (вернее, мостов). По каждому мосту можно перемещаться в обе стороны. Был разработан план очередности строительства мостов и известно, что после постройки всех мостов можно будет проехать по ним с каждого острова на каждый (возможно, через некоторые промежуточные острова
 
Однако, этот момент может наступить до того, как будут построены все мосты. Вам необходимо определить такое минимальное количество мостов, после строительства которых (в порядке, определенном планом), можно будет попасть с любого острова на любой другой.
 
Входные данные
Первая строка содержит два числа: число островов N (1≤N≤10000) и количество мостов в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера городов, которые соединяет очередной мост в плане.
 
Выходные данные
Программа должна вывести единственное число - минимальное количество построенных мостов, после которого можно будет попасть с любого острова на любой другой.

Ввод Вывод
4 5
1 2
1 3
2 3
3 4
4 1
4

https://informatics.msk.ru/mod/statements/view3.php?id=1089&chapterid=1375#1

Ребра

Система непересекающихся множеств

Есть n вершин неориентированного графа, в нем же нет ребер. В граф постепенно добавляются m ребер. 
После каждого добавления ребра требуется узнать количество компонент связности.
В графе могут быть петли и кратные ребра.

Входные данные:
В первой строке два числа  - n и m (1 <= n <= 300000, 0  <= m <= 500000) - количество вершин графа и количество добавляемых ребер. 
В следующих m строках по два числа u, v (1 <= u, v <= n) - они значат, что в граф добавили ребро (u, v).
Выходные данные:
После каждого добавления ребра выведите количество компонент связности графа.

Ввод Вывод
3 2
1 2
2 3
2
1
3 6
1 1
2 2
3 3
1 1
2 2
1 2
3
3
3
3
3
2

(с) Ибрахим Ахмад, 2018