Cod sursa(job #2369905)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 6 martie 2019 09:43:04
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int nMax = 100000;
vector<pair<int, int>> g[nMax + 5];
int n, m;
int use[nMax + 5];
stack<int> st;
vector<int> sol;

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    for (int i = 1; i <= n; i++)
        if (g[i].size() % 2 == 1) {
            fout << -1 << '\n';
            return 0;
        }
    st.push(1);
    while(!st.empty()) {
        if (g[st.top()].size()) {
            int nod = g[st.top()].back().first;
            int edge = g[st.top()].back().second;
            g[st.top()].pop_back();
            if (!use[edge]) {
                st.push(nod);
                use[edge] = 1;
            }
        } else {
            sol.push_back(st.top());
            st.pop();
        }
    }
    for (int i = 0; i < sol.size() - 1; i++)
        fout << sol[i] << ' ';
    fout << '\n';
    return 0;
}