Cod sursa(job #2368224)

Utilizator alexkosaAlex Kosa alexkosa Data 5 martie 2019 14:41:04
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int n,m,vizm[500003];
vector<pair<int,int> >g[100003];

void euler()
{
    for(int i=1;i<=n;i++)
        if((int)g[i].size()%2)
        {fout<<"-1";
            break;}
        else{
            int st[100003];
            int vf=1;
            vector<int>sol;
            st[vf]=1;
            while(vf>0)
            {
                int nod=st[vf];
                if(g[nod].size()==0)
                {
                    sol.push_back(nod);
                    vf--;
                }
                else
                {
                    int muchie=g[nod].back().second;
                    int to=g[nod].back().first;
                    g[nod].pop_back();
                    if(vizm[muchie]==0)
                    {
                        vizm[muchie]=1;
                        st[++vf]=to;
                    }
                }
        
            }
            for(vector<int> :: iterator it=sol.begin();it!=sol.end()-1;it++)
                fout<<*it<<" ";
        }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        g[x].push_back(make_pair(y,i));
        g[y].push_back(make_pair(x,i));
    }
    euler();
    
}