Cod sursa(job #2163888)

Utilizator HuskyezTarnu Cristian Huskyez Data 12 martie 2018 20:22:14
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 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);

struct fuck{
    int nod;
    int nrMuchii;
};

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

int vecini(int nod)
{
    int r = 0;
    for(int i=0; i<graph[nod].size(); i++){
        if(!taiat[nod][i])
            r++;
    }
    return r;
}

void dfsIteratv(int start)
{
    for(st.push(start); !st.empty();){
        int x = st.top();
        if(!graph[x].size()){
            st.pop();
            ciclu.push_back(x);
            continue;
        }
        int nextOnSt = graph[x][0];
        st.push(nextOnSt);
        graph[x].erase(graph[x].begin());
        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);
        if(x!=y){
            graph[y].push_back(x);
        }
        grad[x]++;
        grad[y]++;
        taiat[x].resize(graph[x].size());
        taiat[y].resize(graph[y].size());
    }

    for(int i=1; i<=n; i++){
        if(grad[i] & 1){
            out << "-1\n";
            return 0;
        }
    }

    dfsIteratv(1);

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


    return 0;
}