Cod sursa(job #2073093)

Utilizator DawlauAndrei Blahovici Dawlau Data 22 noiembrie 2017 18:21:16
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#include<list>
#include<stack>
#include<deque>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int NMAX=100005;
list<int>g[NMAX];
deque<int>cycle;
int n,m;
void read_data(){
    int from,to;
    fin>>n>>m;
    while(m--){
        fin>>from>>to;
        g[from].push_back(to);
        g[to].push_back(from);
    }
}
bool eulerian(){
    int i,x;
    for(i=1;i<=n;++i)
        if(g[i].size()%2)
            return false;
    return true;
}
void get_cycle(){
    int current_node,nextnode;
    stack<int>stk;
    stk.push(1);
    list<int>::iterator it;
    while(!stk.empty()){
        current_node=stk.top();
        if(g[current_node].size()){
            nextnode=g[current_node].front();
            g[current_node].pop_front();
            for(it=g[nextnode].begin();*it!=current_node;++it);
            g[nextnode].erase(it);
            stk.push(nextnode);
        }
        else{
            cycle.push_front(current_node);
            stk.pop();
        }
    }
}
void print_cycle(){
    cycle.pop_back();
    while(!cycle.empty()){
        fout<<cycle.front()<<' ';
        cycle.pop_front();
    }
}
int main(){
    read_data();
    if(!eulerian())
        fout<<-1;
    else{
        get_cycle();
        print_cycle();
    }
}