Cod sursa(job #1425122)

Utilizator Denisa13Stefan Denisa Denisa13 Data 26 aprilie 2015 18:31:22
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <queue>

#define NMAX 100005

using namespace std;

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

vector <int> G[NMAX];
vector <int>::iterator it;
stack <int> stiva;
queue <int> coada;
int n,m;
bool viz[NMAX];

void bfs(int nod)
{
    viz[nod]=1;
    coada.push(nod);
    while(coada.empty()==0)
    {
        int x=coada.front();
        for(int i=0;i<G[x].size();i++)
            if(viz[G[x][i]]==0)
            {
                coada.push(G[x][i]);
                viz[G[x][i]]=1;
            }
        coada.pop();
    }
}

void euler (int nod)
{

    while(G[nod].empty()==0)
    {
        int vecin=G[nod].back();
        G[nod].pop_back();
        it=find(G[vecin].begin(),G[vecin].end(),nod);
        int pozitie=it-G[vecin].begin();
        G[vecin][pozitie]=G[vecin].back();
        G[vecin].pop_back();
        euler(vecin);
        stiva.push(nod);
    }
}

int main()
{
    f>>n>>m;
    int x,y,i,ok=1;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    i=1;
    while(i<=n && ok==1)
    {
        if(G[i].size()%2!=0)
            ok=0;
        i++;
    }
    if(ok==0)
        g<<"-1";
    else
    {
        bfs(1);
        for(i=1;i<=n;i++)
            if(viz[i]==0)
            {
                ok=0;
                break;
            }
        if(ok==0)
            g<<"-1";
        else
        {
            int nod=1;
            euler(nod);
            while(stiva.empty()==0)
            {
                g<<stiva.top()<<' ';
                stiva.pop();
            }
        }
    }
    return 0;
}