Cod sursa(job #1327920)

Utilizator c0rn1Goran Cornel c0rn1 Data 27 ianuarie 2015 15:57:30
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
#define NMAX 100005

using namespace std;

vector<int> v[NMAX];
stack<int> s;
int viz[NMAX], sol[NMAX];
int n, m;

void read()
{
    int x, y;
    scanf("%d %d", &n, &m);
    for (int i=1; i<=m; i++){
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

void dfs(int i)
{
    viz[i] = 1;
    for (vector<int>::iterator it = v[i].begin(); it != v[i].end(); ++it)
        if (!viz[*it])
            dfs(*it);
}

int conex()
{
    dfs(1);
    for (int i=1; i<=n; i++)
        if (!viz[i])
            return 0;
    return 1;
}

int gradImpar()
{
    for (int i=1; i<=n; i++)
        if (v[i].size()%2 != 0)
            return 1;
    return 0;
}

void ciclueuler()
{
    s.push(1);
    int x, y;
    while (!s.empty()){
        x = s.top();
        if (v[x].size() == 0){
            sol[++sol[0]] = x;
            s.pop();
        }
        else{
            y = v[x][v[x].size()-1];
            s.push(y);
            v[x].pop_back();
            for (int j = 0; j < v[y].size(); j++)
                if (v[y][j] == x)
                {
                    v[y].erase(v[y].begin() + j);
                    break;
                }
        }
    }
    for (int i=1; i<=sol[0]; ++i){
        printf("%d ", sol[i]);
    }
}

int main()
{
    freopen("ciclueuler.in",  "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    read();
    if (!conex() || gradImpar()){
        printf("-1\n");
        return 0;
    }
    ciclueuler();

    return 0;
}