Cod sursa(job #3365937)

Utilizator alexkAlexandru Kelemen alexk Data 28 septembrie 2026 08:36:16
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
const int NMax=1e5, MMax=5e5;
int n, m, a, b;
vector<vector<pair<int,int>>> adj(NMax+5);
vector<int> gr(NMax+5), vizN(NMax+5), vizM(MMax+5), sol;

void dfs(int nod)
{
    vizN[nod]=1;
    for(auto nxt : adj[nod])
        if(!vizN[nxt.first])
            dfs(nxt.first);
}

void fleury(int nod)
{
    while(adj[nod].size()>0)
    {
        int nxt=adj[nod].back().first;
        int nxt_edge=adj[nod].back().second;
        adj[nod].pop_back();
        if(!vizM[nxt_edge])
        {
            vizM[nxt_edge]=1;
            fleury(nxt);
        }
    }
    sol.push_back(nod);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        gr[a]++;
        gr[b]++;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    dfs(1);

    /// TEOREMA: eulerian=conex + toate gradele pare
    int ok=1;
    for(int i=1;i<=n;i++)
        if(vizN[i]==0 || gr[i]%2==1)
            ok=0;

    if(ok==0)
        cout<<-1;
    else
    {
        fleury(1);
        sol.pop_back();
        for(auto nod : sol)
            cout<<nod<<' ';
    }

    return 0;
}