Cod sursa(job #2239231)

Utilizator NewGloryMihnea Andreescu NewGlory Data 10 septembrie 2018 11:28:54
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

const int N=100000+5;
const int M=500000+5;

int n,m;
int sum[M];
vector<int>g[N];
bool used[M];
vector<int>print;

inline void go(int a)
{
    while(!g[a].empty())
    {
        int id=g[a].back();
        g[a].pop_back();
        if(used[id]==0)
        {
            used[id]=1;
            go(sum[id]-a);
        }
    }
    print.push_back(a);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        sum[i]=a+b;
        g[a].push_back(i);
        g[b].push_back(i);
    }
    for(int i=1;i<=n;i++)
        if(g[i].size()&1)
            cout<<"-1\n", exit(0);
    go(1);
    print.pop_back();
    for(auto x:print)
        cout<<x<<" ";
    cout<<"\n";
    return 0;
}
/**

**/