Cod sursa(job #2337168)

Utilizator MarinPeptenaruMarin Vasile Peptenaru MarinPeptenaru Data 5 februarie 2019 22:51:09
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int nx = 100001;
vector < int > v[nx];
vector < int > s;
stack < int >st;
bitset < nx > viz;
int n,m,i,j;
void dfs (int nod)
{
    viz.set(nod);
    for(vector < int > :: iterator it = v[nod].begin(); it!=v[nod].end(); it++)
        if(!viz.test(*it))
            dfs(*it);
}
void euler()
{
    st.push(1);
    while(!st.empty())
    {
        int x = st.top();
        if(v[x].size())
        {
            int y = v[x].back();
            v[x].pop_back();
            v[y].erase(find(v[y].begin(),v[y].end(),x));
            st.push(y);
        }
        else
        {
            st.pop();
            s.push_back(x);
        }
    }
}
int main()
{
    in>>n>>m;
    for(;m;m--)
    {
        in>>i>>j;
        v[i].push_back(j);
        v[j].push_back(i);
    }
    dfs(1);
    for(int i=1; i<=n; i++)
        if(v[i].size()%2==1 || !viz.test(i))
    {
        out<<-1;
        return 0;
    }
    euler();
    for(vector < int > :: iterator it = s.begin(); it!=s.end()-1; it++)
        out<<*it<<' ';
    return 0;
}