Cod sursa(job #758082)

Utilizator BitOneSAlexandru BitOne Data 14 iunie 2012 13:00:17
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <stack>
#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;

const int N_MAX=100011;
const int bSize=(1<<14)|1;

stack<int> S;
vector<int> r;
vector<int> G[N_MAX];
vector<int>::const_iterator it, iend;
int bIndex;
char buffer[bSize];

bool canHaveE(int N)
{
    int i, count;
    queue<int> Q;
    bool was[N_MAX]={false};

    for(i=1; i <= N; ++i)
        if(G[i].size()&1)
            return false;
    was[1]=true;
    for(Q.push(1), count=N-1; !Q.empty(); Q.pop())
    {
        i=Q.front();
        for(it=G[i].begin(), iend=G[i].end(); it < iend; ++it)
            if(false == was[*it])
            {
                --count;
                if(0 == count)
                    return true;
                was[*it]=true;
                Q.push(*it);
            }
    }
    return false;
}
void Euler(int x)
{
    int y;

    while(!G[x].empty())
    {
        y=G[x].back();
        G[x].pop_back();
        G[y].erase(find(G[y].begin(), G[y].end(), x));
        S.push( x );
        x=y;
    }
}
void Read(istream& in, int& x)
{
    if(-1 == bIndex)
    {
        in.read(buffer, bSize);
        bIndex=0;
    }
    while(buffer[bIndex] < '0' || buffer[bIndex] > '9')
        if(++bIndex == bSize)
        {
            in.read(buffer, bSize);
            bIndex=0;
        }
    for(x=0; buffer[bIndex] >= '0' && buffer[bIndex] <= '9'; )
    {
        x=x*10+buffer[bIndex]-'0';
        if(++bIndex == bSize)
        {
            in.read(buffer, bSize);
            bIndex=0;
        }
    }
}
int main()
{
    int N, M, x, y;
    ifstream in("ciclueuler.in");
    ofstream out("ciclueuler.out");

    for(Read(in, N), Read(in, M); M; --M)
    {
        Read(in, x); Read(in, y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    if(!canHaveE(N))
    {
        out<<"-1\n";
        return EXIT_SUCCESS;
    }
    x=1;
    do {
            Euler(x);
            r.push_back(x=S.top()); S.pop();
       }while(!S.empty());
    copy(r.rbegin(), r.rend(), ostream_iterator<int>(out, " "));
    out<<'\n';
    return EXIT_SUCCESS;
}