Cod sursa(job #1594568)

Utilizator AlexVolatiluVoicu Alex AlexVolatilu Data 9 februarie 2016 16:18:37
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int g[100002];
vector<int> v[100002];
stack<int> st;
queue<int> c;

void ciclue(int x)
{
    int y;
    vector<int>::iterator itr,fin;
    st.push(x);
    while(!st.empty())
    {
        x=st.top();
        if(v[x].empty())
        {
            st.pop();
            c.push(x);
        }
        else
        {
            //remove links
            y=v[x].back();
            v[x].pop_back();

            st.push(y);

            itr=v[y].begin();
            fin=v[y].end();
            while(itr!=fin)
            {
                if(*itr==x)
                {
                    v[y].erase(itr);
                    break;
                }
                itr++;
            }
        }
    }
    while(!c.empty())
    {
        printf("%d ",c.front());
        c.pop();
    }
}

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    int n,m,i,x,y;
    char ok=1;
    scanf("%d%d",&n,&m);
    for(i=0; i<m; i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
        g[x]++;
        g[y]++;
    }
    i=1;
    while(ok && (i<=n))
    {
        if(g[i]%2==1||g[i]==0) ok=0;
        i++;
    }
    if(ok==0)
    {
        printf("-1");
        return 0;
    }

    ciclue(1);

    return 0;
}