Cod sursa(job #1318357)

Utilizator dianaa21Diana Pislaru dianaa21 Data 15 ianuarie 2015 21:25:16
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
using namespace std ;

ifstream is("ciclueuler.in") ;
ofstream os("ciclueuler.out") ;

vector <bool> viz;
vector <int> answ, V[100010], g;
stack <int> S;
queue <int> Q;

int N, M ;

void Read() ;
void Solve() ;
void OUT() ;
void Solve(int x) ;
bool Ok() ;
void BFS() ;

int main()
{
    vector<int> ::iterator it;
    Read();
    BFS();

    if(!Ok())
        os << -1;
    else
    {
        int x = 1 ;

        do {
            Solve(x);
            x = S.top();
            S.pop();
            answ.push_back(x);

        }while( !S.empty() ) ;

        for(it = answ.begin(); it!= answ.end(); ++it)
            os << *it << ' ';
    }

    is.close() ;
    os.close() ;
    return  0 ;
}

void Read()
{
    int x, y;
    is >> N >> M;
    g.resize(N+1);
    viz.resize(N+1, true);
    for(int i = 1; i <= M; ++i)
    {
        is >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
        g[x]++, g[y]++;
    }
}
void BFS()
{
    vector<int> ::iterator it;
    int nod;
    viz[1] = true;
    Q.push(1);
    while(!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        for(it = V[nod].begin(); it != V[nod].end(); ++it)
            if(!viz[*it])
                viz[*it] = true, Q.push(*it);
    }
}
bool Ok()
{
    for(int i = 1 ; i <= N ; ++ i)
        if(!viz[i] || g[i]%2)
            return false ;
    return true ;
}
void Solve(int x)
{
    vector<int> ::iterator it;
    int y;
    while(true)
    {
        if( V[x].empty() )
            break ;

        y = V[x][V[x].size()- 1];
        S.push(x) ;
        V[x].pop_back() ;

        for(it = V[y].begin(); it != V[y].end(); ++it)
            if(*it == x)
            {
                V[y].erase(it);
                break ;
            }

        x = y;
    }
}