Cod sursa(job #1897982)

Utilizator saba_alexSabadus Alex saba_alex Data 1 martie 2017 19:39:03
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAX = 100005;

int x, y, n, m;
int from[MAX], to[MAX];
vector < int > G[MAX];
bool viz[MAX];
stack < int > stiva;
vector < int > sol;
int nod, bun;

void ciclueuler(){

    stiva.push(1);
    while(!stiva.empty()){

        nod = stiva.top();
        if(G[nod].size()){

            int next = G[nod].back();
            G[nod].pop_back();

            if(viz[next])
                  continue;

            viz[next] = 1;
            if(nod == from[next])
                bun = to[next];
            else
                bun = from[next];
            stiva.push(bun);
        }
        else{
            stiva.pop();
            sol.push_back(nod);
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x >> y;
        G[x].push_back(i);
        G[y].push_back(i);
        from[i] = x;
        to[i] = y;
    }

    for(int nod = 1; nod <= n; ++nod){
        if(G[nod].size() % 2){
            fout << "-1";
            return 0;
        }
    }

    ciclueuler();

    for(auto it: sol){
        fout << it << ' ';
    }

    return 0;
}