Cod sursa(job #980759)

Utilizator vlad96Vlad Zuga vlad96 Data 5 august 2013 16:00:10
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<vector>
#include<stack>
#include<list>

using namespace std;

const int Nmax = 100009;
const int Mmax = 500009;

ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int N, M;
stack <int> S;
list <int> G[Nmax];

void read()
{
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
       int X; int Y;
       f >> X >> Y;
       G[X].push_back(Y);
       G[Y].push_back(X);
    }
}

void euler(int Nod)
{
    while(!G[Nod].empty())
    {
        int Y = G[Nod].front();
        S.push(Nod);
        G[Nod].pop_front();

        for(list <int> ::iterator it = G[Y].begin(); it != G[Y].end(); it++)
        {
            if(*it == Nod)
            {
                G[Y].erase(it);
                break;
            }
        }
        Nod = Y;
    }
}

int main()
{
    int Number = 0;
    read();

    for(int i = 1; i <= N; ++i)
    {
        if(G[i].size() % 2)
        {
            g << -1;
            return 0;
        }
    }

    S.push(1);
    do
    {

        int X = S.top();
        S.pop();
        Number++;
        euler(X);
        if(Number != M + 1)
        g << X <<" ";
    }
    while(S.empty() != true );

    f.close(); g.close();
    return 0;
}