Cod sursa(job #2690577)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 24 decembrie 2020 17:15:12
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define NMAX 100003
#define pb push_back

using namespace std;

vector<vector<int> >v(NMAX),d(NMAX);
vector<bool>viz(NMAX,0);
vector<int>ans;

void euler(int nod){

    while(!v[nod].empty()){

        int e=v[nod].back();
        v[nod].pop_back();
        int a=d[nod].back();
        d[nod].pop_back();


        if(!viz[e]){
            viz[e]=1;

            euler(a);
        }
    }

    ans.pb(nod);

}

int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    int n,m;
    scanf("%d%d",&n,&m);


    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].pb(i);
        v[y].pb(i);
        d[x].pb(y);
        d[y].pb(x);

    }

    int ok=1;
    for(int i=1;i<=n;i++)
        if(v[i].size()%2==1)
            ok=0;

    if(!ok)
        printf("%d",-1);
    else{
        euler(1);

        for(int i=0;i<ans.size()-1;i++)
            printf("%d ",ans[i]);
    }


    return 0;
}