Cod sursa(job #992933)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 2 septembrie 2013 20:04:47
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <iostream>
using namespace std;
const int Nmax = 100005;
const int Mmax = 500005;

#define st first
#define dr second
#define pb push_back
#define mp make_pair
#define FOR(i,a,b) for(int (i) = (a) ; i <= (b) ; ++i)

pair<int,int> vertex[Mmax];
vector<int>answer,lvrtx[Nmax];
bitset< Mmax > used;

int N,M,pas;

inline void DFS(int k){
    for(vector<int>::iterator it = lvrtx[k].begin(); it != lvrtx[k].end(); ++it){
        if(used[*it] == false){ // marchez muchia ca folosita
        used[*it] = true;
        ++pas;
        DFS(vertex[*it].st+vertex[*it].dr-k);
        }
    }
    answer.push_back(k);// cand ma intorc notez din ce nod vin
}
inline int eulerian(){
    FOR(i,1,N)
        if(lvrtx[i].size() & 1)return 0;
    return 1;
}
int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);

    scanf("%d %d",&N,&M);
    int x,y;

    FOR(i,1,M){
        scanf("%d %d",&x,&y);
        vertex[i]=mp(x,y); // imi salvez muchiile
        lvrtx[x].pb(i); // imi notez ce muchie pot folosi din nodul x respectiv y
        lvrtx[y].pb(i);
    }
    if(eulerian()){
    DFS(1);
    FOR(i,0,answer.size()-1)
        printf("%d ",answer[i]);
    }
    else printf("-1");
    return 0;
}