Cod sursa(job #1509676)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 24 octombrie 2015 10:50:39
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#define FOR(a,b,c) for(int a=b; a<=c; ++a)
#define FOE(a,b,c) for(int a=b; a<c; ++a)
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n, m, st[500010], a[500010], nrs, nr, x, y, ok, nrv;

vector<int> v[100010];

void euler(int x){
    int y;
    st[++nrs]=x;

    while(nrs>0){

                x=st[nrs];
    if(v[x].size()!=0)
    {
        y=v[x].back();
        st[++nrs]=y;
        v[x].pop_back();
        FOE(i,0,v[y].size())
            if(v[y][i]==x)
            {
                v[y].erase(v[y].begin()+i);
                break;
            }

    }
    else
       {
         nrs--;
       a[++nrv]=x;
       }
}
    }

int main(){
    f>>n>>m;
    FOR(i,1,m)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    FOR(i,1,n)
        if(v[i].size()%2==1)
        {
            g<<"-1\n";
            return 0;
        }
    FOR(i,1,n)
        if(v[i].size()!=0)
        {
            euler(i);
            break;
        }
    if(nrv!=m+1)
    {
        g<<"-1\n";
        return 0;
    }
    FOR(i,1,nrv-1)
        g<<a[i]<<' ';
    return 0;
}