Cod sursa(job #1637427)

Utilizator grimmerFlorescu Luca grimmer Data 7 martie 2016 17:14:43
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int NMAX = 100000;

vector<int>G[NMAX + 5];
int grad[NMAX + 5];
stack<int> st;

void CicluEuler(int u){
    int v, j;
    while(!G[u].empty()){
        st.push(u);
        j = (int)G[u].size();
        v = G[u][j - 1];
        G[u].pop_back();
        G[v].erase( find( G[v].begin(), G[v].end(), u ) );
        u = v;
    }
}

int main()
{
    int i, n, m, u, v;
    bool ok;
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++i){
        scanf("%d%d", &u, &v);

        G[u].push_back(v);
        G[v].push_back(u);

        ++grad[u];
        ++grad[v];
    }

    ok = 1;
    for(i = 1; i <= n; ++i){
        if(grad[i] != 0 && grad[i] % 2 != 0)
            ok = 0;
    }

    if(ok == 1){
        u = 1;

        do{

           CicluEuler(u);
           u = st.top();
           st.pop();
           printf("%d ", u);

        }while(!st.empty());

    }
    else
        printf("-1");
    return 0;
}