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


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

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

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

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

В неориентированный взвешанный граф добавляют ребра. Напишите программу, которая в некоторые моменты находит сумму весов ребер в компоненте связности.
 
Входные данные
В первой строке записано два числа 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

Яблоки

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

У Даши есть 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