Cod sursa(job #1416615)

Utilizator tudi98Cozma Tudor tudi98 Data 8 aprilie 2015 15:42:43
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define dim 100005

int N,M;
vector <int> v[dim];
int grad[dim];
vector <int> Sol;
stack <int> S;

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

    fin >> N >> M;

    for(int i = 1; i <= M; i++){
        int x,y;
        fin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        ++grad[x];
        ++grad[y];
    }

    for(int i = 1; i <= N; i++)
        if(grad[i]&1){
            fout << -1;
            return 0;
        }

    S.push(1);

    while(!S.empty()){
        int u = S.top();

        if(!v[u].empty()){
            int k = v[u].back();
            v[u].pop_back();

            for(int i = 0; i < v[k].size(); i++)
                if(v[k][i] == u){
                    v[k].erase(v[k].begin()+i);
                    break;
                }

            S.push(k);
            continue;
        }

        Sol.push_back(u);
        S.pop();
    }

    for(int i = 0; i < Sol.size() - 1; i++)
        fout << Sol[i] << " ";

}