Cod sursa(job #2322169)

Utilizator DawlauAndrei Blahovici Dawlau Data 17 ianuarie 2019 14:44:08
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <stack>
#include <list>

using namespace std;

class InParser{

    private:

        static const int buffSZ = (1 << 15);
        ifstream File;
        int buffPos;
        char buff[buffSZ];

        void _advance(){

            if(++buffPos == buffSZ){

                File.read(buff, buffSZ);
                buffPos = 0;
            }
        }

    public:
        InParser(const char *FileName){

            File.open(FileName);
            buffPos = buffSZ - 1;
        }

        InParser& operator >>(int &no){

            while(!isdigit(buff[buffPos]))
                _advance();
            no = 0;
            while(isdigit(buff[buffPos])){

                no = no * 10 + buff[buffPos] - '0';
                _advance();
            }
            return *this;
        }
};

InParser fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

const int VMAX = 1e5;

bool isEulerian(const list <int> adjList[1 + VMAX], const int &V){

    for(int node = 1; node <= V; ++node)
        if(adjList[node].size() % 2)
            return false;
    return true;
}

int main(){

    list <int> adjList[1 + VMAX];
    int V, E;

    fin >> V >> E;

    for(; E; --E){

        int from, to;
        fin >> from >> to;

        adjList[from].push_back(to);
        adjList[to].push_back(from);
    }

    if(!isEulerian(adjList, V)){

        fout << -1;
        return 0;
    }

    stack <int> Stack;
    Stack.push(1);

    while(!Stack.empty()){

        int node = Stack.top();

        if(!adjList[node].empty()){

            int nextNode = adjList[node].front();
            adjList[node].pop_front();

            auto it = adjList[nextNode].begin();
            for(; *it != node; ++it);
            adjList[nextNode].erase(it);

            Stack.push(nextNode);
        }
        else{

            fout << Stack.top() << ' ';
            Stack.pop();
        }
    }
}