Cod sursa(job #601573)

Utilizator vendettaSalajan Razvan vendetta Data 7 iulie 2011 00:28:46
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

//typedef vector <int> ::iterator it;
//typedef list <int> :: iterator li;

vector <int> gf[100005];
int i, j, n, m,x, gr[100005];
queue<int>c;

void euler( int nod ){
    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(){
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        gf[x].push_back(y);
        gf[y].push_back(x);
        gr[x]++;gr[y]++;
    }
    c.pop();
    for (i=1;i<=n;++i)
        if (gr[i]%2){
            printf("%c",-1);
            return 0;
        }
    euler( 1 );
    //c.pop();
    //for (queue<int>::iterator it=c.begin();it!=c.end();++it) printf("%d ",*it);

    while (!c.empty()){
        //c.pop();
        printf("%d ",c.front());
        c.pop();
    }
    return 0;
}