Cod sursa(job #2681919)

Utilizator poparobertpoparobert poparobert Data 7 decembrie 2020 12:59:51
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ciclueuler.in");
ofstream cout("ciclueuler.out");
int n,m,ok,a,b;
vector <int> stiva;
bool okmch[500001];
struct muchie{
    int cap,ind;
};
muchie aux;
vector<muchie> muchii[100001];
void dfs(int a)
{
    for(int i=muchii[a].size()-1;i>=0;i--)
    {
        if(okmch[muchii[a][i].ind]==0)
        {
            okmch[muchii[a][i].ind]=1;
            dfs(muchii[a][i].cap);
        }
        else
        {
            if(i==muchii[a].size()-1)
                muchii[a].pop_back();
        }
    }
    stiva.push_back(a);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        aux.cap=b;
        aux.ind=i;
        muchii[a].push_back(aux);
        if(muchii[a].size()%2==1)
            ok++;
        else
            ok--;
        aux.cap=a;
        muchii[b].push_back(aux);
        if(muchii[b].size()%2==1)
            ok++;
        else
            ok--;
    }
    if(ok!=0)
    {
        cout<<-1;
        return 0;
    }
    dfs(1);
    if(stiva.size()!=m+1||stiva[stiva.size()-1]!=stiva[0])
    cout<<-1;
    else
    for(int i=0;i<stiva.size();i++)
    {
        cout<<stiva[i]<<' ';
    }
    return 0;
}