Cod sursa(job #1708787)

Utilizator UPB_Darius_Rares_SilviuPeace my pants UPB_Darius_Rares_Silviu Data 27 mai 2016 22:46:40
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100005

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

int N, M;
vector <int> G[NMAX], sol;
stack <int> st;

void euler(int node) {
    st.push(node);

    while (st.size()) {
        int currentNode = st.top();

        if (G[currentNode].size()) {
            int last = G[currentNode].back();
            for (int i = 0; i < (int)G[last].size(); ++i) {
                if (G[last][i] == currentNode) {
                    swap(G[last][i], G[last][G[last].size() - 1]);
                    G[last].pop_back();
                }
            }

            st.push(last);
            G[currentNode].pop_back();
        } else {
            sol.push_back(currentNode);
            st.pop();
        }
    }
}

int main() {
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i) {
        if (G[i].size() & 1) {
            g << -1 << '\n';
            return 0;
        }
    }

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