Cod sursa(job #2059919)

Utilizator MarinPeptenaruMarin Vasile Peptenaru MarinPeptenaru Data 7 noiembrie 2017 19:03:59
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 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 i)
{
    viz.set(i);
    for(vector < int > :: iterator it=v[i].begin(); it!=v[i].end(); it++)
        if(!viz.test(*it))
            dfs(*it);
}
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)==false || 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;
}