Cod sursa(job #2092130)

Utilizator MarinPeptenaruMarin Vasile Peptenaru MarinPeptenaru Data 21 decembrie 2017 08:29:13
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

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