Cod sursa(job #1018174)

Utilizator teoionescuIonescu Teodor teoionescu Data 28 octombrie 2013 22:49:18
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<vector>
using namespace std;
#define foreach(it,G) for(typeof(G.begin()) it=G.begin();it!=G.end();++it)
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int Nmax = 100005;
struct stack{
    int Stack[Nmax],K;
    void push(int x){Stack[++K]=x;}
    void pop(){K--;}
    int empty(){return K==0;}
    int top(){return Stack[K];}
} St;
vector<int> G[Nmax],S;
int N,M;
int mark[Nmax],grad[Nmax];
void DFS(int i){
    mark[i]=1;
    foreach(it,G[i]) if(!mark[*it]) DFS(*it);
}
int Eulerian(){
    DFS(1);
    for(int i=1;i<=N;i++) if(!mark[i] || grad[i]%2==1) return 0;
    return 1;
}
void remove_edge(int a,int b){
    G[a].erase(G[a].begin());
    foreach(it,G[b]) if(*it==a){
        G[b].erase(it);
        return;
    }
}
void Euler(int i){
    while(G[i].size()){
        int son=G[i].front();
        remove_edge(i,son);
        St.push(i);
        i=son;
    }
}
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int a,b;
        in>>a>>b;
        G[a].push_back(b); grad[a]++;
        if(a!=b)
        G[b].push_back(a); grad[b]++;
    }
    if(!Eulerian()){
        out<<-1;
        return 0;
    }
    int v=1;
    do{
        Euler(v);
        v=St.top(); St.pop();
        S.push_back(v);
    } while(!St.empty());
    foreach(it,S) out<<*it<<' ';
    return 0;
}