Cod sursa(job #1625425)

Utilizator forever16Alex M forever16 Data 2 martie 2016 18:53:52
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>

#define maxn 500005
#define maxn1 100005
using namespace std;
    ifstream in("ciclueuler.in");
    ofstream out("ciclueuler.out");

vector <int> v[maxn1];
int nr;
int a[maxn], d[maxn], sol[maxn];

void St(int x, int y)
{   int l = v[x].size();

    for(int i = 0; i < l; i++)
        if(v[x][i] == y)
        {v[x][i] = v[x][l-1];
    v[x].pop_back();
    return;
}
}

void Euler(int x)
{
    int nod, nod2;
    int k = 1;
    a[1] = 1;

    while(k)
    {   nod = a[k];

    while(v[nod].size())
    {   nod2 = v[nod][0];
    St(nod, nod2);
    St(nod2, nod);
    nod = nod2;

    k++;
    a[k] = nod;
    }

    nr++;
    sol[nr] = a[k];
    k--;

    }
}

int main()
{   int n, m, x, y;

    in >> n >> m;

    for(int i = 1; i <= m; i++)
    {   in >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
    d[x]++, d[y]++;
    }


    for(int i = 1; i <= n; i++)
        if(d[i] % 2 == 1) {out << "-1"; return 0; }

    Euler(1);

    for(int i = 1; i <= nr; i++)
        out << sol[i] << " ";
    return 0;
}