Cod sursa(job #949673)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 14 mai 2013 16:42:38
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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[Nmax], dr[Nmax], traseu[Mmax];
///st[i] = capatul stang al muchiei i
///dr[i] = capatul drept al muchiei i
inline void Citire()
{
    int m ,i;
    ifstream f(In);
    f >> n >> m;
    for( i = 1 ; i <= m; i++)
    {
        f>> st[i] >> dr[i];
        graf[ st[i] ].pb(i);
        graf[ dr[i] ].pb(i);
    }
}
inline bool Este_Eulerian()
{
    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)//daca muchia nu este utilizata
        {
            uz[*it] = true;//o marcam ca fiind utilizata
            Dfs(st[*it]+dr[*it]-nod);//mergem in celalat capat al muchiei
        }
    traseu[++traseu[0]] = nod;
}
int main()
{
    Citire();
    ofstream g(Out);
    if(Este_Eulerian()==0)
    {
        g<<"-1\n";
        g.close();
        return 0;
    }
    Dfs(1);
    int i;
    for(i = 1 ;i <= traseu[0];i++)
        g<<traseu[i]<<" ";
    g<<"\n";
    g.close();
    return 0;
}