Cod sursa(job #3302793)

Utilizator andrei.nNemtisor Andrei andrei.n Data 11 iulie 2025 12:17:06
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

pair<int,int> edge[500005];
vector<int> v[100005];
bitset<500005> bit;
vector<int> idx[100005];
int ciclu[500005];
int pos = 0;
int deg[100005];

void euler(int node)
{
    while(!v[node].empty())
    {
        int son = v[node].back();
        int e = idx[node].back();
        v[node].pop_back();
        idx[node].pop_back();
        if(bit[e])
        {
            bit[e] = 0;
            euler(son);
        }
    }
    ciclu[++pos] = node;
}

signed main()
{
    ifstream fin ("ciclueuler.in");
    ofstream fout ("ciclueuler.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n, m; fin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        int a, b; fin>>a>>b;
        edge[i] = make_pair(a, b);
        v[a].push_back(b);
        v[b].push_back(a);
        idx[a].push_back(i);
        idx[b].push_back(i);
        bit[i] = 1;
        ++deg[a];
        ++deg[b];
    }
    for(int i=1; i<=n; ++i)
        if(deg[i] & 1)
        {
            fout<<"-1";
            return 0;
        }
    euler(1);
    for(int i=1; i<pos; ++i)
        fout<<ciclu[i]<<' ';
    return 0;
}