Cod sursa(job #872491)

Utilizator razvan.popaPopa Razvan razvan.popa Data 6 februarie 2013 08:30:00
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include<iostream>
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<algorithm>
#define INF (1 << 30)
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define nxt (*it)
#define type int
#define FORi(i,a,b)\
   for(int i=a; i<=b; ++i)
#define FORir(i,a,b)\
   for(int i=a; i>=b; --i)
#define FORr(g)\
   for(vector<type>::reverse_iterator it=g.rbegin(); it!=g.rend(); ++it)
#define FOR(g)\
   for(vector<type>::iterator it=g.begin(); it!=g.end(); ++it)
#define infile "ciclueuler.in"
#define outfile "ciclueuler.out"
#define nMax 100005
using namespace std;

vector < int > v[nMax], Euler;

bitset < nMax > used;

int N, M;

void read(){
    ifstream f(infile);

    f >> N >> M;

    int x, y;
    while(M--){
        f >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }

    f.close();
}

void DFS(int x){
    used[x] = true;

    FOR(v[x])
       if(!used[nxt])
          DFS(nxt);
}

void solve(){
    DFS(1);

    FORi(i,1,N)
       if(!used[i] || v[i].size() & 1)
          return;

    stack < int > S;

    int x = 1;
    do{
        while(!v[x].empty()){
            int y = v[x].back();
            v[x].pop_back();

            FOR(v[y])
               if(nxt == x){
                   v[y].erase(it);
                   break;
               }

            S.push(x);
            x = y;
        }

        x = S.top();
        S.pop();

        Euler.pb(x);
    }while(!S.empty());
}

void print(){
    ofstream g(outfile);

    if(!Euler.size())
       g << "-1\n";
    else
       FOR(Euler)
          g << nxt << " ";

    g.close();
}

int main(){
    read();
    solve();
    print();

    return 0;
}