Cod sursa(job #3197693)

Utilizator devilexeHosu George-Bogdan devilexe Data 27 ianuarie 2024 11:52:27
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int MAXN = 1e5;

list<int> G[MAXN + 1];
int N, M;
int st[5 * MAXN + 1], k;

int main()
{
    fin >> N >> M;
    int a, b;
    while(M--) {
        fin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    for(int i = 1; i <= N; ++i)
        if(G[i].empty() || G[i].size() % 2 == 1)
        {
            fout << "-1";
            return 0;
        }
    
    st[k++] = 1;
    while(k) {
        int v = st[k-1];
        while(!G[v].empty()) {
            int w = G[v].front();
            // stergem muchia
            G[v].pop_front();
            G[w].erase(find(G[w].begin(), G[w].end(), v));
            st[k++] = w;
            v = w;
        }
        fout << st[--k] << ' ';
    }
    return 0;
}