Cod sursa(job #1909038)

Utilizator AhileGigel Frone Ahile Data 7 martie 2017 11:29:27
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

ifstream f ("ciclueuler.in");
ofstream g ("ciclueuler.out");

int const MAXSIZE = 100010;
int const MAXM = 500010;

int n, m, x, y;
vector<int> ans;
vector<int> graph[MAXSIZE];
stack<int> st;

int solve () {
    st.push(1);
    while (!st.empty()) {
        int node = st.top();
        if (graph[node].size() != 0) {
            int adj = graph[node].back();
            graph[node].pop_back();
            int aux = 0;
            for (int i = 0; i < graph[adj].size(); i++) {
                if (graph[adj][i] == node && aux == 0) {
                    graph[adj].erase(graph[adj].begin() + i);
                    aux++;
                }
            }
            st.push(adj);
        } else {
            ans.push_back(node);
            st.pop();
        }
    }

}

int main () {
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (graph[i].size() % 2) {
            out << -1;
            return 0;
        }
    }
    solve();
    for (int i = 0; i < ans.size() - 1; i++)
        out << ans[i] << " ";
}