Cod sursa(job #2361641)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 2 martie 2019 17:35:59
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include<bits/stdc++.h>
using namespace std;

const int maxN=(1e5)+5;

vector<int> eulercyc;
multiset<int> v[maxN];
bool seen[maxN];

inline void euler(int nod)
{
    seen[nod]=1;
    while(!v[nod].empty())
    {
        int son=*v[nod].begin();
        v[nod].erase(v[nod].begin());
        v[son].erase(v[son].find(nod));
        euler(son);
    }
    eulercyc.push_back(nod);
}

int n,m,x,y;
int deg[maxN];

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

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

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

    for(int i=1;i<=n;i++)
        if(deg[i]%2)
    {
        printf("-1\n");
        return 0;
    }

    euler(1);


    for(int i=1;i<=n;i++)
        if(!seen[i])
    {
        printf("-1\n");
        return 0;
    }

    for(auto it:eulercyc)
        printf("%d ",it);

    printf("\n");

    return 0;
}