Cod sursa(job #2662139)

Utilizator modulopaulModulopaul modulopaul Data 23 octombrie 2020 16:18:32
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#define MAXN 100001
#define MAXM 500001

using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
struct muc{
    int dest;
    bool went;
};
vector <muc> MC[MAXM];
queue <int> myq;
stack <int> myst;
int grad[MAXN],nrgoodgrad;
int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        muc x,y;
        fin>>x.dest>>y.dest;
        y.went=0;
        x.went=0;
        grad[x.dest]++;
        if(grad[x.dest]%2==0) nrgoodgrad++;
        else nrgoodgrad--;
        grad[y.dest]++;
        if(grad[y.dest]%2==0) nrgoodgrad++;
        else nrgoodgrad--;
        MC[x.dest].push_back(y);
        MC[y.dest].push_back(x);
    }
    if(nrgoodgrad!=0){
        fout<<-1;
        return 0;
    }
    myst.push(1);
    while(!myst.empty()){
        int nod=myst.top();
        bool out=false;
        for(int i=0;i<MC[nod].size() and out==false;i++){
            if(MC[nod][i].went==0){
                myst.push(MC[nod][i].dest);
                MC[nod][i].went=1;
                out=true;
            }
        }
        if(out==false){
            myst.pop();
            myq.push(nod);
        }
    }
    while(!myq.empty()){
        fout<<myq.front()<<' ';
        myq.pop();
    }
    return 0;
}