Cod sursa(job #2072124)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 21 noiembrie 2017 14:09:15
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int N = 100005;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n,m;
vector <int> V[N];
void stergere(int a , int b)
{
    vector <int>::iterator it;
    for(it = V[a].begin(); it != V[a].end(); it++)
    {
        if(*it == b)
        {
            V[a].erase(it);
            break;
        }
    }
}
bool viz[N];
int nrviz;
void conex(int p)
{
    viz[p] = 1;
    nrviz++;
    for(int i = 0; i< V[p].size(); i++)
    {
        int nx = V[p][i];
        if(viz[nx]==0)
        {
            conex(nx);
        }
    }
}
stack <int> s;
vector <int> vect;
void euler()
{
    s.push(1);
    while(!s.empty())
    {
        int vf = s.top();
        if(!V[vf].empty())
        {
            int nx = V[vf].back();
            stergere(nx,vf);
            V[vf].pop_back();
            s.push(nx);
        }
        else
        {
            vect.push_back(vf);
            s.pop();
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i = 1; i<= m; i++)
    {
        int x,y;
        f>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    bool ok = 1;
    for(int i = 1; i<= n; i++)
    {
        int val = V[i].size();
        if(val%2 ==1)
        {
            g<<"-1";
            return 0;
        }
    }
    conex(1);
    if(nrviz != n)
    {
        g<<"-1";
        return 0;
    }
    euler();
    int sz = vect.size();
    for(int i =0; i< sz-1; i++)
    {
        g<<vect[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}