Cod sursa(job #2326493)

Utilizator SweetHumanAvram Gheorghe SweetHuman Data 23 ianuarie 2019 16:39:47
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;
ifstream f1("ciclueuler.in");
ofstream f2("ciclueuler.out");
bitset<500005> viz;
vector<pair<int,int>> muchii;
vector<int> a[100005],afisat;
stack<int> noduri;
int n,m;

void explorare(int start){
    noduri.push(start);
    while(!noduri.empty()){
        if(a[noduri.top()].empty()){
            afisat.push_back(noduri.top());
            noduri.pop();
            continue;
        }
        if(viz[a[noduri.top()].back()]==false){
            viz[a[noduri.top()].back()]=true;
            auto much = muchii[a[noduri.top()].back()];
            a[noduri.top()].pop_back();
            if(much.first!=noduri.top()){
                noduri.push(much.first);
            }else{
                noduri.push(much.second);
            }
        }else{
            a[noduri.top()].pop_back();
        }
    }
}



int main() {
    f1>>n>>m;
    int x,y;
    for(int i=0;i<m;i++) {
        f1 >> x >> y;
        a[x].push_back(i);
        a[y].push_back(i);
        muchii.emplace_back(x, y);
    }
    for(const auto &i : a){
        if(i.size()%2!=0){
            f2<<"-1";
            return 0;
        }
    }
    explorare(1);
    afisat.pop_back();
    for(auto i : afisat){
        f2<<i<<" ";
    }
    return 0;
}