Cod sursa(job #1409745)

Utilizator ArhivaArhiva Infoarena Arhiva Data 30 martie 2015 18:14:47
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;
const int Nmax = 100005;
const int Mmax = 500005;
vector< int >g[Nmax];
bitset< Mmax >uz;
int n, Left[Mmax], Right[Mmax], path[Mmax];
inline void Read()
{
    int m ,i;
    ifstream f("ciclueuler.in");
    f >> n >> m;
    for( i = 1 ; i <= m; i++)
    {
        f>> Left[i] >> Right[i];
        g[Left[i]].push_back(i);
        g[Right[i]].push_back(i);
    }
}
inline bool IsEuler()
{
    int i;
    for(i = 1;i <= n ;i++)
        if(g[i].size()&1)
            return false;
    return true;
}
inline void Dfs(int nod)
{
    for(auto it = g[nod].begin();it != g[nod].end();it++)
        if(uz[*it]==false)
        {
            uz[*it] = true;
            Dfs(Left[*it]+Right[*it]-nod);
        }
    path[++path[0]] = nod;
}
inline void Write()
{
    ofstream g("ciclueuler.out");
    if(IsEuler()==0)
    {
        g<<"-1\n";
        g.close();
        return ;
    }
    Dfs(1);
    for(int i = path[0];i>=1;i--)
        g<<path[i]<<" ";
    g<<"\n";
    g.close();
}
int main()
{
    Read();
    Write();
    return 0;
}