Cod sursa(job #702686)

Utilizator GaborGabrielFMI - GabrielG GaborGabriel Data 2 martie 2012 07:52:59
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

vector<int> v[120006];
queue<int> q;
long long n,m,i,j,a,b,grad[120006];

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

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        grad[a]++,grad[b]++;
    }
    for(i=1;i<=n;i++) if(grad[i]%2) {g<<-1<<'\n';return 0;}
    euler(1);
    q.pop();
    while(!q.empty())
    {
        g<<q.front()<<' ';
        q.pop();
    }
    f.close();
    g.close();
    return 0;
}