Cod sursa(job #2590685)

Utilizator DimaTCDima Trubca DimaTC Data 28 martie 2020 18:18:15
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include<bits/stdc++.h>
#define N 100030
#define pii pair<int,int>
#define x first
#define y second

using namespace std;

int n,m,k,a[N];
stack<int>S;
vector<pii>V[N];
bool u[N*6];

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

    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        int x,y; cin>>x>>y;
        V[x].push_back({y,i});
        V[y].push_back({x,i});
    }

    S.push(1);
    while (S.size()) {
        int st=S.top();// cout<<x<<"!";

        if (V[st].size()) {
            int y=V[st].back().x;
            int idx=V[st].back().y;
            if (!u[idx]) {
                u[idx]=1;
                S.push(y);
            }
            V[st].pop_back();
        } else {
            S.pop();
            a[++k]=st;
        }
    }
    if (k!=m+1) return cout<<-1,0;
    for (int i=k; i>1; --i) cout<<a[i]<<" ";
    return 0;
}