Cod sursa(job #1912831)

Utilizator Harsan_SabinHarsan Sabin Harsan_Sabin Data 8 martie 2017 10:53:13
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <stack>
#define NMAX 100001
#define MMAX 500001

using namespace std;

ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");

int n,m,a,b,cu,k,mk;

int m1[MMAX],m2[MMAX];

bool Viz[MMAX];

list<int> Gf[NMAX];
queue<int> Q;
stack<int> St;

int main()
{
    cin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        if(i==50000)
            a=a;
        cin>>a>>b;
        m1[++k]=a;
        m2[k]=b;
        Gf[a].push_back(k);
        Gf[b].push_back(k);
    }

    for(int i=1;i<=n;++i)
        if(Gf[i].size()%2)
        {
            cout<<-1;
            return 0;
        }

    St.push(1);
    while(!St.empty())
    {
        cu=St.top();
        if(!Gf[cu].empty())
        {
            mk=Gf[cu].back();
            if(!Viz[mk])
            {
                if(cu==m1[mk])
                    St.push(m2[mk]);
                else
                    St.push(m1[mk]);
                Viz[mk]=1;
            }
            Gf[cu].pop_back();
        }
        else
        {
            Q.push(cu);
            St.pop();
        }
    }

    while(!Q.empty())
    {
        cout<<Q.front()<<' ';
        Q.pop();
    }

    return 0;
}