Cod sursa(job #1318392)

Utilizator retrogradLucian Bicsi retrograd Data 15 ianuarie 2015 21:54:01
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<vector>
#include<stack>

#define MAXN 100005
#define MAXM 500005

using namespace std;

typedef int var;

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

struct Edge {
    var n; var i;
    Edge(var a, var b) {
        n = a; i = b;
    }
};

vector<Edge> G[MAXN];
bool VIZ[MAXM];var vi;
var n, m;
var DEG[MAXN];
Edge e(0,0);

void dfs(var node) {
    for(vector<Edge>::iterator it=G[node].begin(); it!=G[node].end(); ++it) {
        e = *it;
        if(!VIZ[e.i]) {
            VIZ[e.i] = 1;
            dfs(e.n);
        }
    }
    fout<<node<<" ";
}

bool VIZN[MAXN];
void conex(var node) {
    VIZN[node] = 1;
    for(vector<Edge>::iterator it = G[node].begin(); it!=G[node].end(); ++it) {
        if(!VIZN[(*it).n]) {
            conex((*it).n);
        }
    }

}

void citire() {
    var a, b;
    fin>>n;
    fin>>m;
    while(m--) {
        fin>>a>>b;
        ++vi;
        DEG[a]++;
        DEG[b]++;
        G[a].push_back(Edge(b, vi));
        G[b].push_back(Edge(a, vi));
    }
}

int main() {
    //Decl

    //Prog
    citire();
    for(var i=1; i<=n; i++) {
        if(DEG[i]%2) {
            fout<<-1;
            return 0;
        }
    }
    conex(1);

    for(var i=1; i<=n; i++) {
        if(!VIZN[i]) {
            fout<<-1;
            return 0;
        }
    }

    for(vector<Edge>::iterator it=G[1].begin(); it!=G[1].end(); ++it) {
        e = *it;
        if(!VIZ[e.i]) {
            VIZ[e.i] = 1;
            dfs(e.n);
        }
    }
    return 0;
}