Cod sursa(job #3162152)

Utilizator vladsoartavlad sofronea vladsoarta Data 28 octombrie 2023 14:20:07
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
int i,n,m,nr;

vector<int>rsp;

struct nodus
{
    int nxt,nrmuc;
};

bool vazut[500001];
vector<nodus> graf_muchii[100001];

void eulerian(int nodincep)
{
    stack<int> stk;
    stk.push(nodincep);

    while(!stk.empty())
    {
        int nod=stk.top();
        if(!graf_muchii[nod].empty())
        {
            nodus muchie = graf_muchii[nod].back();
            graf_muchii[nod].pop_back();
            if(!vazut[muchie.nrmuc])
            {
                vazut[muchie.nrmuc]=1;
                stk.push(muchie.nxt);
            }
        }
        else
        {
            stk.pop();
            rsp.push_back(nod);

        }
    }
}

bool prea_mult_impar()
{

    for(i=1; i<=n; i++)
    {
        if(graf_muchii[i].size()%2==1)
        {
            return 0;
        }

    }

    return 1;

}
/*bool conex()
{
    bool viz[100001]= {0};
    int nodviz=1;
    queue<int> que;
    que.push(1);
    viz[1]=1;

    while(!que.empty())
    {
        int nod=que.front();
        que.pop();

        for(auto vecin:graf_muchii[nod])
        {

            if(!viz[vecin.nod])
            {
                nodviz++;
                viz[vecin.nod]=1;
                que.push(vecin.nod);
            }

        }


    }
    return nodviz==n;
}
*/
int main()
{
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {

        int x,y;
        cin>>x>>y;
        graf_muchii[x].push_back({y,i});
        graf_muchii[y].push_back({x,i});

    }

    /*if(!conex())
    {
        cout<<-1;
        return 0;
    }
    */
    if(!prea_mult_impar())
    {
        cout<<-1;
        return 0;
    }

    eulerian(1);
    for(i=0; i<(int)rsp.size()-1; i++)
        cout<<rsp[i]<<" ";

    return 0;
}