Cod sursa(job #3216901)

Utilizator MilannRosu Mihai Milann Data 20 martie 2024 11:48:22
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
    #include <fstream>
    #include <vector>
    #define NMAX 100005
    #define MMAX 500005

    using namespace std;

    typedef pair<int, int> pii;

    ifstream cin("ciclueuler.in");
    ofstream cout("ciclueuler.out");

    int n, m, x, y;
    vector <pii> g[NMAX];
    bool sel[MMAX];
    vector <int> sol;
    int grad[NMAX];

    void dfs(int node) {
        while (!g[node].empty()) {
            auto it = g[node].back();
            g[node].pop_back();

            if (!sel[it.second]) {
                sel[it.second] = true;
                dfs(it.first);
            }
        }
        sol.push_back(node);
    }

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

        for (int i = 1; i <= m; i++) {
            cin >> x >> y;
            g[x].push_back({y, i});
            g[y].push_back({x, i});
            grad[x]++, grad[y]++;
        }
        
       for (int i = 1; i <= n; i++) {
            if (grad[i] % 2 != 0) {
                cout << -1;
                return 0;
            }
        }

        dfs(1);

        for (int i = 0; i < sol.size() - 1; i++) {
            cout << sol[i] << ' ';
        }
        
        return 0;
    }