Cod sursa(job #2059951)

Utilizator MarinPeptenaruMarin Vasile Peptenaru MarinPeptenaru Data 7 noiembrie 2017 19:18:33
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

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