Cod sursa(job #1218961)

Utilizator rangerChihai Mihai ranger Data 12 august 2014 23:59:26
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
const int nmax  = 100010;
vector<int> g[nmax],res;
vector<int>::iterator it;
stack<int> st;
int n,m,i,x,y,used[nmax];

void dfs(int v)
{
    used[v]=1;
    for (int i=0;i<g[v].size();i++)
        if (!used[g[v][i]])
        dfs(g[v][i]);
}
bool conex()
{
    dfs(1);
    for (int i=1;i<=n;i++)
        if (!used[i]) return false;
    return  true;
}
bool eulerian()
{
    for (int i=1;i<=n;i++)
        if (g[i].size()&1) return false;
    return conex();
}
void solve()
{
    st.push(1);
    while (!st.empty()) {
        int v = st.top();
        if (g[v].size()==0)
            st.pop(),
            res.push_back(v);
        else  {
                int to = g[v][g[v].size()-1];
                st.push(to);
                g[v].pop_back();
                g[to].erase(find(g[to].begin(),g[to].end(),v));
        }
    }
    for (i=0;i+1<res.size();i++) cout<<res[i]<<" ";
}
int main()
{
    cin>>n>>m;
    for (;m--;) {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    if (!eulerian()) {
        cout<<"-1";
        return 0;
    }
   solve();
    return 0;
}