Cod sursa(job #1916723)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 9 martie 2017 10:13:38
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <stack>

#define Ndim 100001
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int Grad[Ndim];
vector <int> G[Ndim],SOL;
stack <int> Q;
int main()
{
    int n,m,i,a,b,v,w,j;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
        Grad[a]++;Grad[b]++;
    }
    for(i=1;i<=n;i++)
    {
        if(Grad[i]%2==1)
        {
            fout<<-1;
            return 0;
        }
    }
    Q.push(1);
    while(!Q.empty())
    {
        v = Q.top();
        if(G[v].size())
        {
            w = G[v][0];
            Q.push(w);
            G[v].erase(G[v].begin());
            for(j=0;j<G[w].size();j++)
                if(G[w][j] == v)
                {
                    G[w].erase(G[w].begin()+j);
                    break;
                }
        }
        else
        {
            SOL.push_back(v);
            Q.pop();
        }
    }
    for(i=0;i<SOL.size()-1;i++)
        fout<<SOL[i]<<' ';
    return 0;
}