Cod sursa(job #1790913)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 octombrie 2016 21:09:12
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <iostream>
#include <bitset>
#include <vector>

#define pb push_back
#define Nmax 100005
#define Mmax 500005

using namespace std;

int n;
vector< int >graf[Nmax];
bitset< Mmax >uz;
int st[Mmax], dr[Mmax], traseu[Mmax];

inline void read()
{
    int m;

    cin >> n >> m;
    for(int i = 1 ; i <= m; i++)
    {
        cin >> st[i] >> dr[i];
        graf[ st[i] ].pb(i);
        graf[ dr[i] ].pb(i);
    }
}
inline bool euler()
{
    int i;
    for(i = 1;i <= n ;i++)
        if(graf[i].size()&1)
            return false;
    return true;
}
inline void DFS(int nod)
{
    for(vector<int>::iterator it = graf[nod].begin();it != graf[nod].end();it++)
        if(uz[*it]==false)
        {
            uz[*it] = true;
            DFS(st[*it]+dr[*it]-nod);
        }
    traseu[++traseu[0]] = nod;
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);

    cin.sync_with_stdio(false);

    read();

    if(euler()==0)
    {
        cout <<"-1\n";
        return 0;
    }
    DFS(1);
    for(int i = 1 ;i <= traseu[0];i++)
        cout <<traseu[i]<<" ";
    cout <<"\n";
    return 0;
}