Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
0
Indexable
Never
#include <iostream>
#include <vector>

using namespace std;

// Функция для нахождения корня дерева
int find(vector<int>& parent, int i) {
    if (parent[i] == i) {
        return i;
    }
    return find(parent, parent[i]);
}

// Функция для объединения двух множеств
void join(vector<int>& parent, vector<int>& rank, int x, int y) {
    int xRoot = find(parent, x);
    int yRoot = find(parent, y);

    // Если элементы принадлежат одному и тому же множеству
    if (xRoot == yRoot) {
        cout << "ALREADY " << x << " " << y << endl;
        return;
    }

    // Иначе объединяем множества
    if (rank[xRoot] < rank[yRoot]) {
        parent[xRoot] = yRoot;
    } else if (rank[xRoot] > rank[yRoot]) {
        parent[yRoot] = xRoot;
    } else {
        parent[yRoot] = xRoot;
        rank[xRoot]++;
    }
}

// Функция для проверки принадлежности элементов одному множеству
bool check(vector<int>& parent, int x, int y) {
    return find(parent, x) == find(parent, y);
}

int main() {
    int n;
    cin >> n;

    // Инициализируем parent и rank
    vector<int> parent(n);
    vector<int> rank(n, 0);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    cout << "RESET DONE" << endl;

    string command;
    while (cin >> command) {
        if (command == "RESET") {
            cin >> n;
            // Инициализируем parent и rank
            parent.resize(n);
            rank.resize(n, 0);
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            cout << "RESET DONE" << endl;
        } else if (command == "JOIN") {
            int a, b;
            cin >> a >> b;
            join(parent, rank, a, b);
        } else if (command == "CHECK") {
            int a, b;
            cin >> a >> b;
            if (check(parent, a, b)) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }

    return 0;
}