Cod sursa(job #1680020)

Utilizator touristGennady Korotkevich tourist Data 8 aprilie 2016 14:29:29
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define Nmax 100005
#define pb push_back

using namespace std;

vector <int> L[Nmax];
vector <int> ::iterator it[Nmax];
int grad[Nmax],st[5*Nmax],dr[5*Nmax],sol[5*Nmax],top,n;
bool used[5*Nmax],viz[Nmax];

inline void Dfs1(int nod)
{
    viz[nod]=1;
    for(auto it : L[nod])
    {
        int x=st[it]+dr[it]-nod;
        if(viz[x]) continue;
        Dfs1(x);
    }
}

inline bool Conex()
{
    Dfs1(1);
    for(int i=1;i<=n;++i)
        if(!viz[i]) return 0;
    return 1;
}

inline void Dfs(int nod)
{
    while(it[nod]!=L[nod].end())
    {
        if(used[*it[nod]])
        {
            ++it[nod]; continue;
        }
        int x=st[*it[nod]]+dr[*it[nod]]-nod;
        used[*it[nod]]=1; ++it[nod];
        Dfs(x);
    }
    sol[++top]=nod;
}

int main()
{
    int m,i;
    ifstream cin("ciclueuler.in");
    ofstream cout("ciclueuler.out");
    cin>>n>>m;
    for(i=1;i<=m;++i)
    {
        cin>>st[i]>>dr[i];
        L[st[i]].pb(i); L[dr[i]].pb(i);
        ++grad[st[i]]; ++grad[dr[i]];
    }
    for(i=1;i<=n;++i)
        if(grad[i]%2)
        {
            cout<<"-1\n"; return 0;
        }
    if(!Conex())
    {
        cout<<"-1\n"; return 0;
    }
    for(i=1;i<=n;++i) it[i]=L[i].begin();
    Dfs(1);
    for(i=1;i<top;++i) cout<<sol[i]<<" ";
    cout<<"\n";
    return 0;
}