Cod sursa(job #1999240)

Utilizator giotoPopescu Ioan gioto Data 10 iulie 2017 18:14:49
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;

int m, n, Sol[1000005], from[500005], to[500005];
vector <int> v[100005];
stack <int> st;
bool f[500005];
int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for(int i = 1; i <= m ; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        v[x].push_back(i);
        v[y].push_back(i);
        from[i] = x;
        to[i] = y;
    }
    for(int i = 1; i <= n ; ++i)
        if((v[i].size()) & 1) {printf("-1\n"); return 0;}

    st.push(1);
    while(!st.empty()){
        int nod = st.top();
        if(!v[nod].empty()){
            int e = v[nod].back();
            v[nod].pop_back();
            if(f[e] == 0){
                f[e] = 1;
                int next = from[e] ^ to[e] ^ nod;
                st.push(next);
            }
        }
        else{
            st.pop();
            Sol[++Sol[0]] = nod;
        }
    }
    for(int i = 1; i <= Sol[0] ; ++i)
        printf("%d ", Sol[i]);
    return 0;
}