Hướng dẫn giải của [CSES 1134] Prüfer Code

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Mã Prüfer tương ứng với việc chọn gốc cho cây trong đó gốc là đỉnh thứ ~n~ nếu ta coi cha của một đỉnh là đỉnh kề duy nhất của nó khi đỉnh đó bị xóa. Bây giờ, gọi số lượng con trực tiếp của mỗi đỉnh là bậc của đỉnh đó.

Nếu bậc của một đỉnh bằng không, nó không có con và do đó là ứng viên để xóa. Nếu ta lưu các ứng viên trong một priority_queue, chỉ số nhỏ nhất trong hàng đợi tương ứng với đỉnh bị xóa tiếp theo. Sau đó, việc còn lại chỉ là duy trì bậc và hàng đợi giữa các lần xóa.

#include <iostream>
#include <queue>
using namespace std;

const int N = 200001;
int code[N];
int degree[N];

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

    for (int i = 1; i <= n - 2; ++i) {
        cin >> code[i];
        degree[code[i]]++;
    }

    priority_queue<int, vector<int>, greater<int>> leaves;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 0) {
            leaves.push(i);
        }
    }

    for (int i = 1; i <= n - 2; ++i) {
        cout << code[i] << ' ' << leaves.top() << '\n';
        leaves.pop();
        degree[code[i]]--;
        if (degree[code[i]] == 0) {
            leaves.push(code[i]);
        }
    }

    cout << leaves.top() << ' ' << n << endl;
}

Tài liệu tham khảo

Chương trình tham khảo

#include <iostream>
#include <queue>
using namespace std;

const int N = 200001;
int code[N];
int degree[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;

    for (int i = 1; i <= n - 2; ++i) {
        cin >> code[i];
        degree[code[i]]++;
    }

    priority_queue<int, vector<int>, greater<int>> leaves;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 0) {
            leaves.push(i);
        }
    }

    for (int i = 1; i <= n - 2; ++i) {
        cout << code[i] << ' ' << leaves.top() << '\n';
        leaves.pop();
        degree[code[i]]--;
        if (degree[code[i]] == 0) {
            leaves.push(code[i]);
        }
    }

    cout << leaves.top() << ' ' << n << endl;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.