Cod sursa(job #1340239)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 11 februarie 2015 18:16:09
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 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],answer;
stack <int> S;
bool viz[NMAX];

void DFS(int nod)
{
    viz[nod] = true;
    for (int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        if (!viz[vecin])
            DFS(vecin);
    }
}

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

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]++;
    }

    DFS(1);

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

    S.push(1);

    while(!S.empty())
    {
        x = S.top();
        if (v[x].size())
        {
            y = v[x][0];
            eraseEdges(x,y);
            S.push(y);
        }
        else
        {
            answer.push_back(x);
            S.pop();
        }
    }

    for (int i = 0; i < answer.size()-1; ++i)
    {
        g << answer[i] << " ";
    }

    f.close();
    g.close();
    return 0;
}