Cod sursa(job #2145838)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 27 februarie 2018 17:26:09
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#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];

vector <int> q;

void euler(int nod){
    q.push_back(nod);
    while(!q.empty()){
        int nod = q.back();
        sol.push_back(nod);
        viz[nod] = 1;
        q.pop_back();
        
        while(graf[nod].size()){
            int nodc = graf[nod].back().edg;
            int poz = graf[nod].back().viz;
            graf[nod].pop_back();
            if(vizedg[poz])
                continue;
            vizedg[poz] = 1;
            q.push_back(nodc);
            break;
        }
    }
}

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