Cod sursa(job #2145786)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 27 februarie 2018 16:53:49
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 100002

using namespace std;

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

int n, m, x, y;

bool viz[DIM], vizedg[5 * DIM];

vector<int> sol;

struct GRAF{
    int edg;
    int viz;
};

GRAF make_graf(int edg, int viz){
    GRAF x;
    x.edg = edg;
    x.viz = viz;
    return x;
}

vector<GRAF> graf[DIM];

void euler(int nod){
    viz[nod] = 1;
    for(int i = 0; i < graf[nod].size(); ++ i){
        int nodc = graf[nod][i].edg;
        int poz = graf[nod][i].viz;
        if(vizedg[poz])
            continue;
        vizedg[poz] = 1;
        euler(nodc);
    }
    sol.push_back(nod);
}

bool cmp(GRAF a, GRAF b){
    return a.edg < b.edg;
}

int main(int argc, const char * argv[]) {
    in>>n>>m;
    for(int i = 1; i <= m; ++ i){
        in>>x>>y;
        graf[x].push_back(make_graf(y, i));
        graf[y].push_back(make_graf(x, i));
    }
    for(int i = 1; i <= n; ++ i){
        if(graf[i].size() % 2){
            out<<-1;
            return 0;
        }
    }
    euler(1);
    for(int i = 1; i <= n; ++ i)
        if(!viz[i]){
            out<<-1;
            return 0;
        }
    for(vector<int>::iterator it = sol.begin(); it != sol.end() - 1; ++ it)
        out<<*it<<" ";
    return 0;
}