Hướng dẫn giải của [CSES 1691] Mail Delivery

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.

Nhiệm vụ của ta là tìm một chu trình Euler trong đồ thị. Tồn tại một chu trình nếu mọi đỉnh đều có bậc chẵn và tất cả các cạnh đều thuộc cùng một thành phần liên thông.

Đoạn code sau sử dụng quay lui để xây dựng một chu trình Euler. Nó đệ quy tạo ra các chu trình bắt đầu và kết thúc tại cùng một đỉnh, và kết hợp các chu trình đó để tạo thành một chu trình Euler.

Đoạn code chạy trong thời gian ~O(n+m \log n)~ vì sử dụng tập (set) để lưu danh sách kề. Có thể cài đặt cùng một thuật toán trong thời gian ~O(n+m)~ một cách phức tạp hơn bằng cách dùng vector thay vì tập.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

vector<set<int>> graph;
vector<int> cycle;

void fail() {
    cout << "IMPOSSIBLE\n";
    exit(0);
}

void find_cycle(int node) {
    while (!graph[node].empty()) {
        int next_node = *graph[node].begin();
        graph[node].erase(next_node);
        graph[next_node].erase(node);
        find_cycle(next_node);
    }
    cycle.push_back(node);
}

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

    graph.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].insert(b);
        graph[b].insert(a);
    }

    for (int i = 1; i <= n; i++) {
        if (graph[i].size() % 2 != 0) fail();
    }

    find_cycle(1);
    if (cycle.size() != m + 1) fail();

    for (auto node : cycle) {
        cout << node << " ";
    }
    cout << "\n";
}

Tài liệu tham khảo

Chương trình tham khảo

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<int> eu(m), ev(m);
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        eu[i] = a;
        ev[i] = b;
        adj[a].push_back(i);
        adj[b].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        if ((int)adj[i].size() % 2 != 0) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }

    vector<int> ptr(n + 1, 0);
    vector<char> used(m, 0);
    vector<int> st;
    st.push_back(1);
    vector<int> circuit;

    while (!st.empty()) {
        int v = st.back();
        while (ptr[v] < (int)adj[v].size() && used[adj[v][ptr[v]]])
            ptr[v]++;
        if (ptr[v] == (int)adj[v].size()) {
            circuit.push_back(v);
            st.pop_back();
        } else {
            int e = adj[v][ptr[v]++];
            if (used[e])
                continue;
            used[e] = 1;
            int u = eu[e] ^ ev[e] ^ v;
            st.push_back(u);
        }
    }

    if ((int)circuit.size() != m + 1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }

    reverse(circuit.begin(), circuit.end());
    for (int i = 0; i <= m; i++) {
        if (i)
            cout << ' ';
        cout << circuit[i];
    }
    cout << '\n';
    return 0;
}

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.