Cod sursa(job #1379817)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 6 martie 2015 19:39:57
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

const int NMAX = 100005;

using namespace std;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int N,M,grad[NMAX],x,y;
vector <int> v[NMAX];
stack <int> S;

void sterge(int x, int y)
{
    v[x].erase(v[x].begin());
    v[y].erase(find(v[y].begin(),v[y].end(),x));
}

void solve()
{
    S.push(1);

    while (!S.empty())
    {
        int nod = S.top();

        if (v[nod].size())
        {
            S.push(v[nod][0]);
            sterge(nod,v[nod][0]);
        }

        else
        {
            g << nod << " ";
            S.pop();
        }
    }
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        grad[x]++;
        grad[y]++;
    }

    for (int i = 1; i <= N; ++i)
    {
        if (grad[x] % 2 != 0)
        {
            g << "-1";
            return 0;
        }
    }

    solve();
}