Cod sursa(job #2164267)

Utilizator HuskyezTarnu Cristian Huskyez Data 12 martie 2018 22:31:09
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define infile "ciclueuler.in"
#define outfile "ciclueuler.out"

using namespace std;

ifstream in(infile);
ofstream out(outfile);

int n, m;
int x, y;
vector<int> graph[100005];
stack<int> st;
vector<int> ciclu;


void dfsIteratv(int start)
{
    for(st.push(start); !st.empty();){
        int x = st.top();
        if(graph[x].empty()){
            st.pop();
            ciclu.push_back(x);
            continue;
        }
        int nextOnSt = graph[x][0];
        graph[x].erase(graph[x].begin());
        vector<int>::iterator it;
        for(it=graph[nextOnSt].begin(); *it != x; it++);
        graph[nextOnSt].erase(it);
        st.push(nextOnSt);
//        if(x != nextOnSt){
//            if(graph[nextOnSt][0] == x){
//                graph[nextOnSt].erase(graph[nextOnSt].begin());
//            }else{
//                int off = 0;
//                for(int p=graph[nextOnSt][0]; p!=x; off++){
//                    p = graph[nextOnSt][off];
//                }
//                graph[nextOnSt].erase(graph[nextOnSt].begin()+(off-1));
//            }
//        }
    }
}


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() & 1){
            out << "-1\n";
            return 0;
        }
    }

    dfsIteratv(1);

    for(int i=0; i<ciclu.size(); i++){
        out << ciclu[i] << ' ';
    }


    return 0;
}