Cod sursa(job #2492786)

Utilizator mihai2003LLL LLL mihai2003 Data 15 noiembrie 2019 11:44:19
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

struct muchie{
    int x,y;
    int valid;
    muchie(int x_,int y_){
        x=x_;
        y=y_;
        valid=1;
    }
};

const int NMAX=100001;
std::vector<muchie>muchii;
std::vector<int>v[NMAX];
std::vector<int>sol;
int nr[NMAX];
class input_parser{
protected:
    FILE *fin;///Input file
    static const int max_load=1<<10;///Maximum Allocation
    size_t pos;///Index of the buffer
    char buffer[max_load];///Input is being store here
public:
    input_parser():pos(0){}
    input_parser(const char *);///Opens the specified file
    void open(const char *);///^
    template<class T>
    void read(T &);///Read function
    void read(){}
    template<class T,typename ... Args>
    void read(T & ,Args&...args);
    void read(char *,size_t);///Read a string
    inline char next();///Advances the buffer
};

input_parser::input_parser(const char * fName){
    this->fin=fopen(fName,"r");
    this->pos=0;
}

void input_parser::open(const char *fName){
    delete this->fin;
    memset(this->buffer,0,sizeof(this->buffer));
    this->fin=fopen(fName,"r");
    this->pos=0;
}

inline char input_parser::next(){
    if(this->pos==max_load)
            fread(this->buffer,1,max_load,this->fin),this->pos=0;
    return this->buffer[this->pos++];
}

template<class T>
void input_parser::read(T & nr){
    char c;
    int semn=1;
    nr=0;
    c=this->next();
    while(!isdigit(c) && c!='-')
        c=this->next();
    while(c=='-')
        c=this->next(),semn*=-1;
    while(isdigit(c))
        nr=nr*10+c-'0',c=this->next();
    nr*=semn;
}
template<class T,typename ... Args>
void input_parser::read(T & t,Args&...args){
    read(t);
    read(args...);
}

void input_parser::read(char *chp,size_t sz){
    char c;
    c=next();
    while(c==' ' || c=='\n')
        c=next();
    for(size_t i=0;i<sz && c!=' ' && c!='\n';i++)
        chp[i]=c,c=next();
}
input_parser in("ciclueuler.in");
void dfs(int nod){
    while(nr[nod]){
        for(int i=0;i<v[nod].size();i++){
            int m=v[nod][i];
            if(muchii[m].valid){
                muchii[m].valid=0;
                nr[nod]--;
                if(nod==muchii[m].x)
                    nr[muchii[m].y]--,dfs(muchii[m].y);
                else
                    nr[muchii[m].x]--,dfs(muchii[m].x);
                }
        }
    }
    sol.push_back(nod);
}
std::ofstream out("ciclueuler.out");
int main(){
    int n,m;
    in.read(n,m);
    for(int i=0,x,y;i<m;i++){
        in.read(x,y);
        muchii.push_back(muchie(x,y));
        v[x].push_back(muchii.size()-1);
        v[y].push_back(muchii.size()-1);
        nr[x]++;
        nr[y]++;
    }
    for(int i=1;i<=n;i++)
        if(v[i].size()%2==1){
            out<<-1;
            return 0;
        }
    dfs(1);
    sol.pop_back();
    for(int x:sol)
        out<<x<<" ";
    return 0;
}