Cod sursa(job #1496439)

Utilizator elevenstrArina Raileanu elevenstr Data 4 octombrie 2015 22:38:24
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <queue>
using namespace std;
#define MAX 100070
stack <int> S;
vector <int> v[MAX];
int gr[MAX];
vector <int> sol;
bitset <MAX> viz;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
queue <int> Q;
inline  void bfs(int nod)
{
    viz[nod]=1;
    Q.push(nod);
    while(!Q.empty())
    {
        nod=Q.front();
        Q.pop();
        for(vector <int> ::iterator it=v[nod].begin(); it!=v[nod].end(); ++it)
        {
            if(viz[*it]==0)
            {   Q.push(*it);
                viz[*it]=1;

            }

        }
    }
}
inline void euler()
{
    S.push(1);
    while(!S.empty())
    {
        int nod=S.top();
        if(!v[nod].empty())
        {
            int nou=v[nod].back();
            S.push(nou);
            v[nod].pop_back();
            v[nou].erase(find (v[nou].begin(),v[nou].end(),nod));
        }
        else
        {
            sol.push_back(nod);
            S.pop();
        }
    }

}

int main()
{
    int n,m,x,y,i,j;
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
    bfs(1);
    euler();


    for(i=1; i<=n; i++)
        if(gr[i]%2||viz[i]==0)
        {
            out<<-1;
            return 0;

        }
    for(i=0; i<sol.size()-1; i++)
        out<<sol[i]<<" ";



    return 0;
}