Cod sursa(job #3197668)

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

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

const int MAXN = 1e5;

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

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][0];
            // stergem muchia
            G[v].erase(G[v].begin());
            G[w].erase(find(G[w].begin(), G[w].end(), v));
            st[k++] = w;
            v = w;
        }
        if(k > 1)
            fout << st[k-1] << ' ';
        --k;
    }
    return 0;
}