Задача: Система непересекающихся множеств: Начало
Напишите программу, которая будет содержать реализацию структуры данных для совокупности непересекающихся подмножеств (disjoint sets) 2 способами (ранговой эвристики и случайным образом) и обрабатывать запросы таких видов:
RESET n — создать новую серию подмножеств: множество из одного только элемента 0, из одного только элемента 1, и так до множества из одного только элемента n–1 включительно. Если структура уже содержала какую-то другую совокупность непересекающихся подмножеств, вся соответствующая информация утрачивается. На стандартный выход (экран) при этом следует вывести два слова через пробел «RESET DONE».
JOIN j k — объединить подмножества, которым принадлежат элемент j и элемент k. Если элементы и так принадлежали одному подмножеству, вывести на стандартный выход (экран) слово «ALREADY», после него через пробелы те же числа j и k в том же порядке. Если элементы до сих пор принадлежали разным подмножествам, то действие происходит только с данными в памяти, на экран ничего не выводится.
CHECK j k — проверить, одному ли подмножеству принадлежат элемент j и элемент k; вывести на стандартный выход (экран) слово «YES» (если одному) или слово «NO» (если разным).
BREAK - закончить прием запросов.
Входные данные
Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату. Гарантированно, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 200000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n–1, где n — параметр последнего выполненного запроса RESET.
Выходные данные
Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному подмножеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке).
Примечание
Ответы «NO» даются на запросы «CHECK 2 11» и «CHECK 9 1», ответ «ALREADY 4 1» — на второй из запросов «JOIN 4 1» (10-я строка), «YES» — на «CHECK 5 10».
| Ввод |
Вывод |
|
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
BREAK
|
RESET DONE
NO
ALREADY 4 1
NO
YES
|
| Напишите программу ниже |
#include <iostream>
#include <string>
using namespace std;
long long n, x, y, par[100007], rang[100007];
void make_set(int v) {
par[v] = v;
rang[v] = 1;
}
int find_set(int a) {
if (par[a] == a)
return a;
else
return par[a] = find_set(par[a]);
}
void union_sets(int a, int b) {
|
|
|
}
int main()
{
string s;
while (cin >> s) {
if (s == "BREAK")
break;
if (s == "RESET") {
cin >> n;
for (int i = 0; i<n; i++) {
make_set(i);
}
cout << "RESET DONE" << endl;
}
if (s == "JOIN") {
cin >> x >> y;
if(find_set(x)==find_set(y))
cout<<"ALREADY"<<' '<<x<<' '<<y<<endl;
else union_sets(x,y);
}
if (s == "CHECK") {
cin >> x >> y;
if (find_set(x) == find_set(y)) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
|
Ваш ответ: