Cod sursa(job #2073541)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 23 noiembrie 2017 12:07:30
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 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;
struct nod
{
    int nxt,mch;
};
vector <nod> V[N];

bool viz[N];
int nrviz;

stack <int> s;
vector <int> vect;
bool muchii[5*N];

void euler()
{
    s.push(1);
    while(!s.empty())
    {
        int vf = s.top();
        if(!V[vf].empty())
        {
            nod nx = V[vf].back();
            if(muchii[nx.mch] == 0)
            {
                s.push(nx.nxt);
                nrviz++;
                muchii[nx.mch] = 1;
            }
            V[vf].pop_back();
        }
        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,i});
        V[y].push_back({x,i});
    }
    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();
    if(nrviz != m)
    {
        g<<"-1";
        return 0;
    }
    int sz = vect.size();
    for(int i =0; i< sz-1; i++)
    {
        g<<vect[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}