Cod sursa(job #2126044)

Utilizator Y0da1NUME JMECHER Y0da1 Data 8 februarie 2018 23:44:59
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>

#define MAXM 500005

using namespace std;

int N, M;

vector <int> G [100002];
vector <int> ans;
int src [MAXM], dest [MAXM];
bool folosit [MAXM];

int euler (int curr)
{
    //cout<<"AM AJUNS PE NODUL "<<curr<<"\n";
    int succ;   //blowjob
    while(!G[curr].empty())    //nodul nostru are vecini
    {
        succ = G[curr].back();
        //cout<<"SELECTEZ MUCHIA "<<succ<<"\n";
        G[curr].pop_back();
        if(!folosit[succ])
        {
            folosit[succ] = 1;
            if(src[succ] == curr)
                euler(dest[succ]);
            else
                euler(src[succ]);


        }
    }
    ans.push_back(curr);
}


int main()
{
    int x, y;
    ifstream in ("ciclueuler.in");
    ofstream out ("ciclueuler.out");

    in>>N>>M;

    for(int i = 0; i < M; ++i)
    {
        in>>x>>y;
        G[x].push_back(i);
        G[y].push_back(i);
        src[i] = x;
        dest[i] = y;
    }
    for (int i = 1; i <= N; ++i)
        if (G[i].size() & 1)
        {
            out << "-1\n";
            return 0;
        }
    euler(1);


    //avem grad par

    for (int i = 0; i < ans.size() - 1; ++i)
        out<<ans[i]<<" ";
    out<<"\n";

}