Cod sursa(job #1368548)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 2 martie 2015 18:27:57
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
# include <cstdio>
# include <vector>
# include <stack>
# include <algorithm>
# define pb push_back
# define N 100010

using namespace std;

int n,m,x,y;
vector <int> G[N];
vector <int> sol;
stack <int> st;


void ciclu(int x)
{
    st.push(x);
    while(!st.empty())
    {
        int nod=st.top();
        if(G[nod].size())
        {
            int last=G[nod].back();
            G[nod].pop_back();
            st.push(last);
            G[last].erase(find(G[last].begin(),G[last].end(),nod));
        }
        else sol.pb(nod),st.pop();
    }
}

int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d %d", &x, &y);
        G[x].pb(y);
        G[y].pb(x);
    }

    for(int i=1; i<=n; ++i)
        if(G[i].size()&1)
        {
            printf("-1\n");
            return 0;
        }
    ciclu(1);
    for(int i=0; i<sol.size(); ++i)
        printf("%d ", sol[i]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}