Cod sursa(job #2169235)

Utilizator SenibelanMales Sebastian Senibelan Data 14 martie 2018 14:21:04
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int NMAX = 100005;
int N, M;
int impare;
bool UseEdge[NMAX * 5];
vector <int> G[NMAX], sol;
vector <pair <int, int> > Edges;
stack <int> S;


void Read(){
    in >> N >> M;
    for(int i = 0; i < M; ++i){
        int a, b;
        in >> a >> b;
        G[a].push_back(i);
        G[b].push_back(i);
        Edges.push_back(make_pair(a, b));
    }
}

void Solve(){
    S.push(1);
    while(!S.empty()){
        int node = S.top();
        if(!G[node].empty()){
            int edge = G[node].back();
            G[node].pop_back();
            if(!UseEdge[edge]){
                UseEdge[edge] = true;
                int to = (node == Edges[edge].first ? Edges[edge].second : Edges[edge].first);
                S.push(to);
            }
        }
        else{
            S.pop();
            sol.push_back(node);
        }
    }
}

void Print(){
    for(int i = 0; i < sol.size(); ++i)
        out << sol[i] << " ";
    out << "\n";
}


int main(){
    Read();
    for(int i = 1; i <= N; ++i){
        if(G[i].size() % 2){
            out << "-1";
            return 0;
        }
    }
    Solve();
    Print();
    return 0;
}