Cod sursa(job #1336022)

Utilizator rsteliRadu Stelian rsteli Data 6 februarie 2015 13:30:09
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");

#define nmax 100010

int n,m,x,y,gr[nmax],viz[nmax];
vector<int> g[nmax],v;
stack<int> st;
queue<int> q;

void bfs()
{
    int nod;
    vector<int>::iterator it;
    q.push(1);
    viz[1]=1;
    while (!q.empty())
    {
        nod=q.front();
        q.pop();
        for (it=g[nod].begin();it!=g[nod].end();it++)
            if (!viz[*it])
            {
                viz[*it]=1;
                q.push(*it);
            }
    }
}

void sterge(int k,int v)
{
    vector<int>::iterator it;
    gr[k]--;
    gr[v]--;
    g[k].pop_back();
    for (it=g[v].begin();it!=g[v].end();it++)
        if (*it==k)
        {
            g[v].erase(it);
            break;
        }
}

void euler(int k)
{
    int v;
    while (1)
    {
        if (!g[k].size())
            break;
        v=*(g[k].rbegin());
        sterge(k,v);
        st.push(k);
        k=v;
    }
}

int main()
{
    int i,j;
    vector<int>::iterator it;
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
    bfs();
    for (i=1;i<=n;i++)
    {
        if (gr[i]%2==1)
        {
            cout<<-1;
            exit(0);
        }
        if (!viz[i])
        {
            cout<<-1;
            exit(0);
        }
    }
    x=1;
    do
    {
        euler(x);
        x=st.top();
        st.pop();
        v.push_back(x);
    }while (!st.empty());
    for (it=v.begin();it!=v.end();it++)
        cout<<*it<<" ";
}