Cod sursa(job #2711588)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 24 februarie 2021 14:25:12
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int n,m;
list < int > v[100005];
int a,b;
stack < int > s;

int verify_odd() {
    for (int i=1;i<=n;i++) {
        if (v[i].size()%2==1 || v[i].size()==0) {
            return 0;
        }
    }
    return 1;
}

void euler_cycle() {
    s.push(1);
    while (s.empty()==0) {
        int nod = s.top();
        while (v[nod].empty()==0) {
            int nodtoviz = *v[nod].begin();
            v[nod].erase(v[nod].begin());
            v[nodtoviz].erase(find(v[nodtoviz].begin(),v[nodtoviz].end(),nod));
            s.push(nodtoviz);
            nod = nodtoviz;
        }
        g << s.top() << " ";
        s.pop();
    }
}

int main()
{
    f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    if (verify_odd()==0) {
        g << -1;
    }
    else {
        euler_cycle();
    }
    return 0;
}