【題解】CSES 1691 Mail Delivery

【範例】尤拉迴路 (Euler Circuit)
【題目敘述】https://cses.fi/problemset/task/1691/

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, m, a, b;
set <int> st[100005];
vector <int> ans;
 
void dfs(int x){
    while (st[x].size()){
        int now = *st[x].begin();
        st[now].erase(x);
        st[x].erase(now);
        dfs(now);
    }
    ans.push_back(x);
}
 
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        st[a].insert(b);
        st[b].insert(a);
    }
    for (int i = 1; i <= n; i++){
        if (st[i].size() % 2){
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }
    dfs(1);
    if (ans.size() != m+1) cout << "IMPOSSIBLE\n";
    else{
        reverse(ans.begin(), ans.end());
        for (int i:ans){
            cout << i << " ";
        }
        cout << "\n";
    }
}
分享本文 Share with friends