Cod sursa(job #2559399)

Utilizator AnnaLipianuLipianu Ana AnnaLipianu Data 27 februarie 2020 12:05:53
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#define NMAX 100000
#define MMAX 500000
using namespace std;

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

char vaz[MMAX+2];
int stiva[MMAX+2];

struct muchie
{
    int nod,ind;
};

vector <muchie> v[NMAX+2];
vector <int> rez;

int main()
{
    int n,i,m,x,y,varf,gasit;
    muchie a;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>x>>y;
        a.ind=i;
        a.nod=x;
        v[y].push_back(a);
        a.nod=y;
        v[x].push_back(a);
    }
    for(i=1; i<=n; i++)
        if(v[i].size()%2==1)
        {
            cout<<"-1";
            return 0;
        }
    int top=0;
    stiva[++top]=1;
    while(top>0)
    {
        varf=stiva[top];
        gasit=0;
        for(i=(v[varf].size()-1); i>=0 && !gasit; i--)
            if(!vaz[v[varf][i].ind])
            {
                vaz[v[varf][i].ind]=1;
                gasit=1;
                stiva[++top]=v[varf][i].nod;
            }
            else
                v[varf].pop_back();
        if(gasit==0)
        {
            rez.push_back(stiva[top]);
            top--;
        }
    }
    for(vector<int>:: iterator it=rez.begin();(it+1)!=rez.end();it++)
        cout<<*it<<' ';
    return 0;
}