Cod sursa(job #1327916)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 27 ianuarie 2015 15:38:56
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#define MAXN 100005

using namespace std;

vector<int> v[MAXN];
stack<int> st, sol;
vector<bool> viz;
int n, k;

int verifica(int x)
{
    viz[x] = 1;
    if (v[x].size()%2)
        return 0;
    int ok = 1;
    for (int i = 0; i < v[x].size(); i++)
    {
        if (!viz[v[x][i]])
            ok = verifica(v[x][i]);
    }
    return ok;
}

void solve()
{
    st.push(1);
    int top;
    while(!st.empty())
    {
        top = st.top();
        if (v[top].size() == 0)
        {
            sol.push(top);
            st.pop();
        }
        for (int i = 0; i < v[top].size(); i++)
        {
            int vec = v[top][i];
            st.push(vec);
            v[top].erase(v[top].begin() + i);
            cerr << find(v[vec].begin(), v[vec].end(), top) - v[vec].begin() << "\n";
            v[vec].erase(find(v[vec].begin(), v[vec].end(), top));
            break;
        }
    }
    while(!sol.empty())
    {
        printf("%d ", sol.top());
        sol.pop();
    }
}

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

    scanf("%d %d", &n, &k);
    int t1, t2;
    viz.resize(MAXN);
    for (int i = 1; i <= k; i++)
    {
        scanf("%d %d", &t1, &t2);
        v[t1].push_back(t2);
        v[t2].push_back(t1);
    }
    int ol = 0;

    if (!verifica(1))
    {
        printf("-1\n");
        return 0;
    }
     for (int i = 1; i <= n && !ol; i++)
        ol = !viz[i];
    if (ol)
    {
        printf("-1\n"); return 0;
    }
    solve();

    return 0;
}