Cod sursa(job #1696768)

Utilizator superstar1998Moldoveanu Vlad superstar1998 Data 29 aprilie 2016 19:08:38
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100005;
vector <int> G[NMAX];
int grad[NMAX];
stack <int> st;

void euler_valoare(int u)
{
    int v;
    while(!G[u].empty())
    {
        st.push(u);
        v = G[u][G[u].size()-1];
        G[u].pop_back();
        G[v].erase(find(G[v].begin(),G[v].end(),u));
        u=v;
    }
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    int n , m , i,pos1,pos2,u=1;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&pos1,&pos2);
        G[pos1].push_back(pos2);
        G[pos2].push_back(pos1);
        grad[pos1]++;
        grad[pos2]++;
    }
    for(i=1;i<=n;++i)
        if(grad[i] == 0 or grad[i]%2 == 1)
        {
            printf("-1\n");
            return 0;
        }
    do
    {
        euler_valoare(u);
        u=st.top();
        st.pop();
        printf("%d ",u);
    }while(!st.empty());
    return 0;
}