Cod sursa(job #482476)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 3 septembrie 2010 16:44:53
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <stack>
#include <vector>
#define max1 100002
#define max2 500002

using namespace std;

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

vector<int>::iterator it;
vector<int>G[max1];
stack<int> S;
int Sol[max2];
int N,M,i,s,nod,y;
bool ok;

int main()
{
    in>>N>>M;
    while(M--)
    {
        in>>nod>>y;
        G[nod].push_back(y);
        G[y].push_back(nod);
    }
    for(i=1;i<=N;i++)
        if((G[i].size())&1)
        {
            out<<"-1";
            return 0;
        }
    S.push(1);
    while(!S.empty())
    {
        y =S.top();
        if(G[y].size()==0)
            Sol[++s] = y,S.pop();
        else
        {
            nod = G[y].back();
            G[y].pop_back();
            ok = true;
            S.push(nod);
            for(it=G[nod].begin();it!=G[nod].end()&&ok;++it)
                if(*it==y)
                    G[nod].erase(it),ok = false;
        }
    }
    for(i=1;i<=s;i++)out<<Sol[i]<<' ';
    return 0;
}