Cod sursa(job #2297961)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 6 decembrie 2018 20:55:38
Problema Ciclu Eulerian Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
//avoid stackoverflow
#include <iostream>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#define INF (1<<28)
#define Nmax 1000005

using namespace std;

string file="ciclueuler";

ifstream f( (file + ".in").c_str() );
ofstream g( (file + ".out").c_str() );

int n, m;
stack <int> st;
vector <int> v[Nmax], sol;

bool check()
{
    for (int i = 1; i <= n; i++)
        if(v[i].size()%2 == 1) return 0;
    return 1;
}

void euler()
{
    st.push(1);
    while(!st.empty())
    {
        int x=st.top();
        st.pop();
        if(v[x].size())
        {
            int y=v[x].back(); v[x].pop_back();
            for (vector <int> ::iterator it=v[y].begin(); it!=v[y].end(); it++)
            {
                if(*it == x)
                {
                    v[y].erase(it);
                    break;
                }
            }
            st.push(y);
        }
        sol.push_back(x);
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1, x, y; i <= m; i++)
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    if(check() ==  false)
    {
        g << "-1";
        return 0;
    }
    euler();
    for (vector <int> ::iterator it=sol.end()-1; it!=sol.begin(); it--)
        g << *it << " ";
    return 0;
}