Напишите программу, которая будет содержать реализацию структуры данных для совокупности непересекающихся подмножеств (disjoint sets) и обрабатывать запросы таких видов:
RESET n — создать новую серию подмножеств: множество из одного только элемента 0, из одного только элемента 1, и так до множества из одного только элемента n–1 включительно. Если структура уже содержала какую-то другую совокупность непересекающихся подмножеств, вся соответствующая информация утрачивается. На стандартный выход (экран) при этом следует вывести два слова через пробел «RESET DONE».
JOIN j k — объединить подмножества, которым принадлежат элемент j и элемент k. Если элементы и так принадлежали одному подмножеству, вывести на стандартный выход (экран) слово «ALREADY», после него через пробелы те же числа j и k в том же порядке. Если элементы до сих пор принадлежали разным подмножествам, то действие происходит только с данными в памяти, на экран ничего не выводится.
CHECK j k — проверить, одному ли подмножеству принадлежат элемент j и элемент k; вывести на стандартный выход (экран) слово «YES» (если одному) или слово «NO» (если разным).
Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату. Гарантированно, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 200000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n–1, где n — параметр последнего выполненного запроса RESET.
Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному подмножеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке).
| Ввод | Вывод |
|---|---|
RESET 15 JOIN 14 10 JOIN 13 8 JOIN 0 9 JOIN 8 3 JOIN 4 1 JOIN 10 5 JOIN 8 4 CHECK 2 11 JOIN 4 1 JOIN 2 6 CHECK 9 1 JOIN 6 5 CHECK 10 5 |
RESET DONE NO ALREADY 4 1 NO YES |
В неориентированный взвешенный граф добавляют ребра. Напишите программу, которая в некоторые моменты находит сумму весов ребер в компоненте связности.
В первой строке записано два числа \(n\) и \(m\) \((1 \leq n,m \leq 10^6)\) - количество вершин в графе и количество производимых добавлений и запросов. Далее следует \(m\) строк с описанием добавления или запроса. Каждая строка состоит из двух или четырех чисел. Первое из чисел обозначает код операции. Если первое число 1, то за ним следует еще три числа \(x, y, w\). Это означает, что в граф добавляется ребро из вершины \(x\) в вершину \(y\) веса \(w\). \((1 \leq x \leq y \leq n, 1 \leq w \leq 10^3)\). Кратные ребра допустимы. Если первое число 2, то за ним следует ровно одно число \(x\). Это означает, что необходимо ответить на вопрос, какова сумма ребер в компоненте связности, которой принадлежит вершина \(x (1 \leq x \leq 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 |
Дан неориентированный граф. Над ним в заданном порядке производят операции следующих двух типов:
Известно, что после выполнения всех операций типа \(cut\) рёбер в графе не осталось. Найдите результат выполнения каждой из операций типа \(ask\).
Первая строка входного файла содержит три целых числа, разделённые пробелами — количество вершин графа \(n\), количество рёбер \(m\) и количество операций \(k\) \((1 \leq n \leq 50000, 0 \leq m \leq 100000, m \leq k \leq 150000)\).
Следующие \(m\) строк задают рёбра графа; \(i\)-ая из этих строк содержит два числа \(u_i\) и \(v_i\) \((1 \leq u_i,v_i \leq n)\), разделённые пробелами — номера концов \(i\)-го ребра. Вершины нумеруются с единицы; граф не содержит петель и кратных рёбер.
Далее следуют \(k\) строк, описывающих операции. Операция типа cut задаётся строкой "cut \(u\) \(v\)" \((1 \leq u,v \leq n)\), которая означает, что из графа удаляют ребро между вершинами \(u\) и \(v\). Операция типа ask задаётся строкой "ask \(u\) \(v\)" \((1 \leq u,v \leq n)\), которая означает, что необходимо узнать, лежат ли в данный момент вершины \(u\) и \(v\) в одной компоненте связности. Гарантируется, что каждое ребро графа встретится в операциях типа cut ровно один раз.
Для каждой операции ask во входном файле выведите на отдельной строке слово "YES", если две указанные вершины лежат в одной компоненте связности, и "NO" в противном случае. Порядок ответов должен соответствовать порядку операций ask во входном файле.
| Ввод | Вывод |
|---|---|
3 3 7 1 2 2 3 3 1 ask 3 3 cut 1 2 ask 1 2 cut 1 3 ask 2 1 cut 2 3 ask 3 1 |
YES YES NO NO |
От вас требуется определить вес минимального остовного дерева для неориентированного взвешенного связного графа.
В первой строке входных данных находятся числа \(N\) и \(M\) \((1 \leq N \leq 100; 1 \leq M \leq 6000)\), где \(N\) – количество вершин в графе, а \(M\) – количество рёбер. В каждой из последующих \(M\) строк записано по тройке чисел \(A, B, C\), где \(A\) и \(B\) – номера вершин, соединённых ребром, а \(C\) – вес ребра (натуральное число, не превышающее 30000)
Вывести одно число – искомый вес.
| Ввод | Вывод |
|---|---|
3 3 1 2 1 2 3 2 3 1 3 |
3 |
Требуется найти в связном графе остовное дерево минимально веса.
Первая строка входного файла содержит два натуральных числа \(n\) и \(m\) - количество вершин и ребер графа соответственно \((1 \leq n \leq 20000, 0 \leq m \leq 100000)\). Следующие \(m\) строк содержат описание ребер по одному на строке. Ребро номер \(i\) описывается тремя натуральными числами \(b_i\), \(e_i\) и \(w_i\) - номера концов ребра и его вес соответственно \((1 \leq b_i,e_i \leq n, 0 \leq w_i \leq 100000)\).
Граф является связным.
Выведите единственное целое число - вес минимального остовного дерева.
| Ввод | Вывод |
|---|---|
4 4 1 2 1 2 3 2 3 4 5 4 1 4 |
7 |
Ася очень любит животных. Недавно она приобрела \(n\) котят, дала им числовые идентификаторы от \(1\) до \(n\) и поселила в вольере. Вольер представляет собой ряд из \(n\) ячеек, также пронумерованных от \(1\) до \(n\). Cоседние ячейки разделены сетчатыми перегородками, всего в вольере \(n - 1\) перегородок. Изначально в каждой ячейке поселился ровно один котёнок с некоторым номером.
Наблюдая за котятами, Ася заметила, что они очень дружелюбны и некоторые пары живущих в соседних ячейках котят очень хотят играть друг с другом. Чтобы не лишать их этого удовольствия, Ася стала вынимать перегородки между соседними ячейками, делая их более крупными.
В \(i\)-й день Ася делала следующее.
Поскольку Ася не возвращала перегородки, через \(n - 1\) день вольер стал единой ячейкой, в которой обитали все котята. Будучи очень педантичной, Ася записывала в специальный журнал идентификаторы котят \(x_i\) и \(y_i\) для каждого из \(n - 1\) дней.
Вам в руки попал журнал с этой информацией, однако вам неизвестно, как котята были поселены в ячейки изначально. Найдите любое расселение котят по \(n\) исходным ячейкам, не противоречащее данным в журнале.
В первой строке задано целое число \(n\) \((2 \leq n \leq 150000)\) — количество котят.
В следующих \(n−1\) строках заданы пары целых чисел \(x_i, y_i\) \((1 \leq x_i,y_i \leq n,x_i \neq y_i)\) — идентификаторы котят, между ячейками которых была удалена перегородка в день \(i\). Гарантируется, что котята \(x_i\) и \(y_i\) не находятся в одной ячейке по итогам предыдущих объединений ячеек.
Выведите \(n\) различных целых чисел \(p_i\) \((1 \leq p_i \leq n)\), где \(p_i\) — идентификатор котёнка, который изначально жил в ячейке с номером \(i\). Если возможных вариантов ответа несколько, выведите любой из них.
| Ввод | Вывод |
|---|---|
5 1 4 2 5 3 1 4 5 |
3 1 4 2 5 |