Cod sursa(job #1143054)

Utilizator Vladinho97Iordan Vlad Vladinho97 Data 14 martie 2014 17:19:25
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#define nmax 100009
using namespace std;
struct vecini
{
    vector<int> v;
};
vecini g[nmax];
queue<int> q;
stack<int> st;
int deg[nmax];
bool viz[nmax];
void DFS(int nod,int final)
{
    st.push(nod);
    if(nod!=final||deg[nod]>0)
    {
        int i,urm;
        urm=g[nod].v[0];
        deg[urm]--;deg[nod]--;
        for(i=0;i<g[urm].v.size();i++)
            if(g[urm].v[i]==nod)
            {
                g[urm].v.erase(g[urm].v.begin()+i);
                break;
            }
        g[nod].v.erase(g[nod].v.begin()+0);
        DFS(urm,final);
    }
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    int i,j,n,m,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].v.push_back(y);deg[x]++;
        g[y].v.push_back(x); deg[y]++;
    }
    q.push(1);
    viz[1]=true;
    while(q.empty()==0)
    {
        int top=q.front();
        int lung=g[top].v.size();
        for(i=0;i<lung;++i)
        {
            if(viz[g[top].v[i]]==false)
            {
                viz[g[top].v[i]]=true;
                q.push(g[top].v[i]);
            }
        }
        q.pop();
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==false||deg[i]%2!=0)
        {
            printf("-1\n");
            return 0;
        }
    }
    DFS(1,1);
    st.pop();
    while(st.empty()==0)
    {
        while(deg[st.top()]!=0)
        {
            x=st.top();
            st.pop();
            DFS(x,x);
        }
        printf("%d ",st.top());
        st.pop();

    }
}