Cod sursa(job #1790911)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 octombrie 2016 21:06:48
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <bitset>
#include <vector>

#define In "ciclueuler.in"
#define Out "ciclueuler.out"
#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;
    ifstream f(In);
    f >> n >> m;
    for(int i = 1 ; i <= m; i++)
    {
        f>> 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()
{
    read();
    ofstream g(Out);
    f.sync
    if(euler()==0)
    {
        g<<"-1\n";
        return 0;
    }
    DFS(1);
    for(int i = 1 ;i <= traseu[0];i++)
        g<<traseu[i]<<" ";
    g<<"\n";
    return 0;
}