Cod sursa(job #1148574)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 20 martie 2014 21:39:07
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
vector<list<int> > V;
queue<int> Q;
stack<int> ST;
bool used[100001];


int main()
{
    int n,m;
    fin>>n>>m;
    V.resize(n+1);
    for(int i=1 ;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }

    Q.push(1);
    while(!Q.empty())
    {
        int nod = Q.front();
        for(list<int>::iterator it = V[nod].begin(); it != V[nod].end(); it++)
            if(!used[*it])
            {
                Q.push(*it);
                used[*it] = true;
            }
        Q.pop();
    }

    bool ok = true;
    for(int i=1;i<=n && ok;i++)
        if(V[i].size() & 1 || !used[i])
            ok = false;
    if(!ok)
        fout<<-1;
    else
    {
        ST.push(1);
        while(!ST.empty())
        {
            int nod = ST.top();

            if(!V[nod].size())
            {
                fout<<nod<<' ';
                ST.pop();
            }
            else
            {
                int vecin = *V[nod].begin();
                V[nod].erase(V[nod].begin());
                list<int>::iterator it = V[vecin].begin();
                while(*it != nod)
                    it++;

                V[vecin].erase(it);
                ST.push(vecin);
            }

        }


    }

    fin.close();
    fout.close();
    return 0;
}