Hướng giải của Đường đi thám hiểm

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Đây là bài toán tìm đường đi Euler trên đồ thị vô hướng. Điều kiện cần và đủ để đồ thị vô hướng có đường đi Euler là số đỉnh bậc lẻ bằng đúng 2 (hoặc 0 khi là chu trình). Chúng ta bắt buộc phải khởi hành từ một trong hai đỉnh bậc lẻ này. Cài đặt thuật toán Hierholzer từ đỉnh bậc lẻ đó.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<multiset<int>> adj(n + 1);
    vector<int> deg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        if (cin >> u >> v) {
            adj[u].insert(v);
            adj[v].insert(u);
            deg[u]++; deg[v]++;
        }
    }
    int odd_cnt = 0;
    int start = 1;
    for (int i = 1; i <= n; i++) {
        if (deg[i] % 2 != 0) {
            odd_cnt++;
            start = i;
        }
    }
    if (odd_cnt != 0 && odd_cnt != 2) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    vector<int> path;
    stack<int> stk;
    stk.push(start);
    while (!stk.empty()) {
        int u = stk.top();
        if (!adj[u].empty()) {
            int v = *adj[u].begin();
            adj[u].erase(adj[u].begin());
            adj[v].erase(adj[v].find(u));
            stk.push(v);
        } else {
            path.push_back(u);
            stk.pop();
        }
    }
    if ((int)path.size() != m + 1) {
        cout << "IMPOSSIBLE\n";
    } else {
        for (size_t i = 0; i < path.size(); i++) {
            cout << path[i] << (i + 1 == path.size() ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.