Cod sursa(job #2492793)

Utilizator mihai2003LLL LLL mihai2003 Data 15 noiembrie 2019 11:57:41
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.92 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){



        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;

}