Cod sursa(job #2663341)

Utilizator racleta31Andreican Rares racleta31 Data 26 octombrie 2020 09:02:10
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int nmax=1e5+5;
const int mmax=5e5+5;
int n,m, x , y ;
vector <pair<int, int> > a[nmax];
bitset <mmax> used;
queue <int> sol;
void euler(int start)
{
    stack <int> st;
    st.push(start);
    while(st.size())
    {
        int curent = st.top();
        st.pop();
        if(a[curent].size() == 0)
        {
            sol.push(curent);
        }
        else
        {
            auto edge =a[curent].back();

            a[curent].pop_back();
            st.push(curent);
            if(!used[edge.second])
            {
                used[edge.second]=true;
                st.push(edge.first);
            }
        }
    }
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        a[x].push_back({y, i});
        a[y].push_back({x, i});
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i].size()%2 != 0)
        {
            out<< -1;
            return 0;
        }
    }
    euler(1);
    while(sol.size() > 1)
    {
        out << sol.front();
        out << ' ';
        sol.pop();
    }
    return 0;
}