Cod sursa(job #757473)

Utilizator razielreaperMatei Andrei razielreaper Data 12 iunie 2012 10:27:39
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <vector>
#include <deque>
#include<cstring>
using namespace std;
vector<int> g[100020];
deque<int> q;
bool ok;
int n,m,x,y,i,j,k;
char s[100000];
void euler(int nod)
{
    int nod1;
    vector<int>::iterator it;
    q.push_back(nod);
    while(!q.empty()){
        nod=q.front();
        if(g[nod].empty()){q.pop_front();printf("%d ",nod);}
        else{
            nod1=g[nod].back();
            q.push_front(nod1);
            g[nod].pop_back();
            for(it=g[nod1].begin();it!=g[nod1].end();++it)
            if(*it==nod){g[nod1].erase(it);break;}
        }
    }
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=m;++i){
    gets(s);k = strlen(s); ok=true;
        x=0; y=0;
        for(j=0; j<k ; ++j)
             if (s[j]==' ') ok=false;
             else {
                 if (ok) x=x*10 + s[j]-'0'; else y = y*10+s[j]-'0';}
    g[y].push_back(x);
    g[x].push_back(y);
    }
    ok=true;
    for(i=1;i<=n;++i)
    if(g[i].size()%2!=0)ok=false;
    if(ok==false)printf("-1\n");
    else euler(1);
    return 0;
}