Cod sursa(job #2559726)

Utilizator aeliusdincaaelius dinca aeliusdinca Data 27 februarie 2020 15:57:02
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int st[500001];
char vc[500001];
struct muchie
{
    int nod,nr;
};
vector <muchie> v[100002];
vector <int> ras;
int main()
{
    int n,m,x,y,i,k=1,ok,vf;
    muchie a;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        a.nr=i;a.nod=x;
        v[y].push_back(a);
        a.nod=y;
        v[x].push_back(a);
    }
    for(i=1;i<=n;i++)
    {
        if(v[i].size()%2==1)
        {
            out<<"-1";
            return 0;
        }
    }
    st[k]=1;
    while(k>0)
    {
        ok=0;
        vf=st[k];
        for(i=v[vf].size()-1;i>=0&&ok==0;i--)
        {
            if(!vc[v[vf][i].nr])
            {
                vc[v[vf][i].nr]=1;
                ok=1;
                st[++k]=v[vf][i].nod;
            }
            else
                v[vf].pop_back();
        }
        if(ok==0)
        {
            ras.push_back(st[k]);
            k--;
        }
    }
    for(vector<int>::iterator it=ras.begin();(it+1)!=ras.end();it++)
        out<<*it<<" ";
    return 0;
}