Cod sursa(job #2520823)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 9 ianuarie 2020 19:42:05
Problema Ciclu Eulerian Scor 80
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int Nmax = 100000;

vector <int> g[Nmax + 5], sol;
stack <int> st;
int n, m, other;
bool use[Nmax + 5];

void Read(){
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void DFS(int node){
    use[node] = 1;
    for (auto i : g[node])
        if (!use[i])
            DFS(i);
}

int Check(){
    DFS(1);
    for (int i = 1; i <= n; i++)
        if (g[i].size() % 2 || (!use[i] && g[i].size()))
            return 0;
    return 1;
}

void Delete(int node, int other){
    g[node].pop_back();
    g[other].erase(find(g[other].begin(), g[other].end(), node));
}

void Cycle(int node){
    while (!g[node].empty()){
        st.push(node);
        other = g[node].back();
        Delete(node, other);
        node = other;
    }
}

void Solve(){
    int node = 1;
    do{
        Cycle(node);
        node = st.top();
        st.pop();
        sol.push_back(node);
    }while (!st.empty());
}

void Print(){
    for (auto i : sol)
        fout << i << ' ';
    fout << '\n';
}

int main(){
    Read();
    if (!Check()){
        fout << -1 << '\n';
        return 0;
    }
    Solve();
    Print();
    return 0;
}