Cod sursa(job #2462667)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 27 septembrie 2019 18:39:43
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector <pair <int , int> > G[100005];
stack <int> st;
int ans[500005] , viz[500005] , n , m;
int valid()
{
    int i;
    for(i = 1 ; i <= n ; i ++)
        if(G[i].size() % 2 == 1)
            return 0;
    return 1;
}
void euler()
{
    int u , v , ok;
    st.push(1);
    while(!st.empty())
    {
        ok = 0;
        u = st.top();
        while(G[u].size() && viz[G[u].back().first])
            G[u].pop_back();
        if(G[u].size())
        {
            v = G[u].back().second;
            viz[G[u].back().first] = 1;
            G[u].pop_back();
            st.push(v);
            ok = 1;
        }
        if(!ok)
        {
            st.pop();
            if(!st.empty())
                ans[++ ans[0]] = st.top();
        }
    }
}
int main()
{
    freopen("ciclueuler.in" , "r" , stdin);
    freopen("ciclueuler.out" , "w" , stdout);
    int i , u , v;
    scanf("%d%d" , &n , &m);
    for(i = 1 ; i <= m ; i ++)
    {
        scanf("%d%d" , &u , &v);
        G[u].push_back(make_pair(i , v));
        G[v].push_back(make_pair(i , u));
    }
    if(valid())
    {
        euler();
        for(i = 1 ; i <= ans[0] ; i ++)
            printf("%d " , ans[i]);
    }
    else
        printf("-1\n");
    return 0;
}