Cod sursa(job #1403974)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 27 martie 2015 17:57:05
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include<fstream>
#include<vector>
#include<stack>
#include<queue>
#include<iostream>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int NMAX = 100000;

vector<int> v[NMAX + 5];
vector<int> sol;
int viz[NMAX + 5],n,m;

void read()
{

    in>>n>>m;
    int a,b;
    for(int i = 1 ; i <= m ; ++i){
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    in.close();
}

bool conex(){

    queue<int> coada;
    coada.push(1);
    int nr_nod = 0;
    while(!coada.empty()){
        int k = coada.front();
        coada.pop();
        for(int i = 0 ; i < v[k].size() ; ++i)
            if(!viz[v[k][i]]){
                ++nr_nod;
                viz[v[k][i]] = 1;
                coada.push(v[k][i]);
            }
    }
    if(nr_nod != n)
        return false;
    return true;

}

bool grad_par()
{

    for(int i = 1 ;  i <= n ; ++i)
        if(v[i].size()%2)
            return false;
        return true;
}

void sterge(int x,int y)
{

    for(int i = 0 ; i < v[x].size() ; ++i)
        if(v[x][i] == y){
            v[x].erase(v[x].begin() + i);
            return;
        }
}

void euler()
{

    stack<int> st;
    st.push(1);
    int act = 1;
    while(!st.empty()){
        if(!v[act].size()){
            sol.push_back(st.top());
            st.pop();
            if(!st.empty())
                act = st.top();
        }
        else{
            int vc = v[act][0];
            v[act].erase(v[act].begin());
            sterge(vc,act);
            act = vc;
            st.push(vc);
        }
    }
}

void afis(){
    for(int i = 0 ; i < sol.size() ; ++i)
        out<<sol[i]<<" ";
    out.close();
}

bool ok(){
    if(conex() && grad_par())
        return true;
    return false;
}

int main()
{

    read();
    if(!ok())
        out<<-1;
    else{
        euler();
        afis();
    }
    return 0;
}