Cod sursa(job #2169445)

Utilizator JiyuuNoTsubasaMaria Guran JiyuuNoTsubasa Data 14 martie 2018 15:31:54
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector <pair<int,int> >v[500005];
vector <int> a;
int n,m,viz[500005],st[500005],u=-1;
void euler()
{
    st[++u]=1;
    while(u!=-1)
    {
        int nod=st[u];
        if(!v[nod].empty())
        {
            int vf=v[nod].back().first;
            int muchie=v[nod].back().second;
            v[nod].pop_back();
            if(!viz[muchie])
            {
                viz[muchie]=1;
                st[++u]=vf;
            }
        }
        else
        {
            u--;
            a.push_back(nod);
        }
    }
}
    int main()
    {
        in>>n>>m;
        for(int i=1; i<=m; i++)
        {
            int x,y;
            in>>x>>y;
            v[x].push_back({y,i});
            v[y].push_back({x,i});
        }
        int ok=1;
        for(int i=1; i<=n&&ok; i++)
        {
            if(v[i].size()%2!=0)
                ok=0;
        }
        if(!ok)
            out<<-1;
        else
        {
            euler();
            for(int i=a.size()-1; i>=0; i--)
                out<<a[i]<<" ";
        }
        return 0;
    }