Cod sursa(job #978171)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 28 iulie 2013 01:55:41
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int n, m;
vector <int> G[100010];
stack <int> st;

inline void Read()
{
    ifstream f("ciclueuler.in");
    f>>n>>m;
    int i, x, y;
    for (i=1; i<=m; i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    f.close();
}

inline bool Verificare()
{
    for (int i=1; i<=n; i++)
        if (G[i].size() & 1)
            return true;
    return false;
}

inline void Solve()
{
    ofstream g("ciclueuler.out");
    st.push(1);
    int x, y;
    vector <int>::iterator it;
    while (!st.empty())
    {
        x = st.top();
        if (G[x].size())
        {
            y = G[x].back();
            G[x].pop_back();
            for (it = G[y].begin(); it!=G[y].end(); it++)
            {
                if (*it == x)
                {
                    *it = G[y].back();
                    G[y].pop_back();
                    break;
                }
            }
            st.push(y);
        }
        else
        {
            g<<st.top()<<" ";
            st.pop();
        }
    }
    g<<"\n";
    g.close();
}


int main()
{
    Read();
    if (Verificare())
    {
        ofstream g("ciclueuler.out");
        g<<"-1\n";
        g.close();
        return 0;
    }
    Solve();
    return 0;
}