Cod sursa(job #602114)

Utilizator vendettaSalajan Razvan vendetta Data 9 iulie 2011 02:29:31
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstring>
#include <vector>
#include <queue>
#include<fstream>

using namespace std;

ifstream in;
ofstream out;

vector <int>gf[100001];
int grad[100001];
queue<int>c;

void euler( int nod ){
    int x;
    for (;gf[nod].size();){
        x=*gf[nod].begin();
        gf[nod].erase(gf[nod].begin());
        for(vector<int>::iterator it=gf[x].begin();it!=gf[x].end();++it)
            if (*it==nod) {
                gf[x].erase(it);
                break;
            }
        euler(x);
    }
    c.push(nod);
}

int main(){
    int n, m, i, j;
    in.open("ciclueuler.in");
    out.open("ciclueuler.out");
    in>>n>>m;
    memset(grad,0,sizeof(grad));
    //for (i=1;i<=m;i++){
    for(;m;--m){
        int x,y;
        in>>x>>y;
        gf[x].push_back(y);
        gf[y].push_back(x);
        grad[x]++;grad[y]++;
    }
    for (i=1;i<=n;++i)
        if (grad[i]%2){
            out<<"-1\n";
            return 0;
        }
    euler( 1 );
    c.pop();

    while (!c.empty()){
        out<<c.front()<<" ";
        c.pop();
    }
    return 0;

}