Cod sursa(job #3342374)

Utilizator BidonTurtitBezdedan Eric BidonTurtit Data 23 februarie 2026 22:42:10
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <bitset>
#include <queue>
#define NMax 100005
#define MMax 500005
using namespace std;

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

int n, m,to[MMax],from[MMax];
vector <int> vecini[NMax];
queue <int> ciclu;
bitset <MMax> edge;

void euler(int start)
{
    stack <int> temp;
    temp.push(start);
    while(!temp.empty())
    {
        int cur=temp.top();
        if(!vecini[cur].empty())
        {
            int aux=vecini[cur].back();
            vecini[cur].pop_back();
            if(!edge[aux])
            {
                edge[aux]=1;
                if(to[aux]==cur)
                    temp.push(from[aux]);
                else
                    temp.push(to[aux]);
            }
        }
        else
        {
            temp.pop();
            ciclu.push(cur);
        }

    }


}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        vecini[x].push_back(i);
        vecini[y].push_back(i);
        from[i]=x;
        to[i]=y;
    }
    for(int i=1;i<=n;i++)
    {
        if(vecini[i].size()>0 && vecini[i].size()%2==1)
        {
            fout<<"-1";
            return 0;
        }
    }
    euler(1);
    while(ciclu.size()>1)
    {
        fout<<ciclu.front()<<" ";
        ciclu.pop();
    }
    return 0;
}