Cod sursa(job #2169231)

Utilizator SenibelanMales Sebastian Senibelan Data 14 martie 2018 14:19:12
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 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 Count(int a){
    if(G[a].size() & 1)
        impare++;
    else
        impare--;
}

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);
        Count(a);
        Count(b);
        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();
            out << node << " " << Edges[edge].first << " " << Edges[edge].second << "\n";
            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();
    if(impare){
        out << "-1\n";
        return 0;
    }
    Solve();
    Print();
    return 0;
}