Cod sursa(job #2172054)

Utilizator victoreVictor Popa victore Data 15 martie 2018 14:51:01
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<vector>
#include<stack>

using namespace std;

int N,M;

const int NMAX = 1e5+5;

vector<int> g[NMAX],sol;
stack<int> st;

struct muchie
{
    int x,y;
}Edges[NMAX*5];

bool VizEdge[NMAX*5];

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

    int i,j,a,b;

    scanf("%d%d",&N,&M);

    for(i = 1 ; i <= M ; ++i)
    {
        scanf("%d%d",&a,&b);
        g[a].push_back(i);
        g[b].push_back(i);
        Edges[i].x = a;
        Edges[i].y = b;
    }

    for(i = 1 ; i <= N ; ++i)
        if( (g[i].size())&1 )
        {
            printf("-1");
            return 0;
        }

    st.push(1);
    int node,ID;

    while(!st.empty())
    {
        node = st.top();
        if(!g[node].empty())
        {
            ID = g[node].back();
            g[node].pop_back();
            if(!VizEdge[ID])
            {
                VizEdge[ID] = 1;
                if(Edges[ID].x == node)
                    st.push(Edges[ID].y);
                else
                    st.push(Edges[ID].x);
            }
        }
        else
        {
            st.pop();
            sol.push_back(node);
        }
    }

    for( i = 0 ; i < sol.size() ; ++i)
        printf("%d ",sol[i]);

    return 0;

}