Cod sursa(job #1130811)

Utilizator robert_stefanRobert Stefan robert_stefan Data 28 februarie 2014 15:44:45
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <vector>
#include <queue>
#include <fstream>
#define IN "ciclueuler.in"
#define OUT "ciclueuler.out"
#define NMAX 100005

using namespace std;

ifstream in(IN);
ofstream out(OUT);

vector <int> G[NMAX];
int n;
bool use[NMAX];
vector <int> sol;

inline void DFS(int nod)
{
    use[nod]=true;
    for(int i=0; i<G[nod].size(); ++i)
        if(!use[G[nod][i]])
            DFS(G[nod][i]);
}

inline void euler(int nod)
{
    while(G[nod].size())
    {
        int aux=G[nod].front();
        G[nod].erase(G[nod].begin());
        bool sw=false;
        for(int i=0; i<G[aux].size() && !sw; ++i)
            if(G[aux][i]==nod)
            {
                G[aux].erase(G[aux].begin()+i);
                sw=true;
            }
        euler(aux);
    }
    sol.push_back(nod);
}

inline bool IsEuler()
{
    int i;
    DFS(1);
    for(i=1; i<=n; ++i)
        if(G[i].size()%2 || !use[i])
            return false;
    return true;
}

int main()
{
    int m, a, b;
    in>>n>>m;
    while(m--)
    {
        in>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    if(IsEuler())
    {
        euler (1);
        for(int i=0; i<sol.size(); ++i)
            out<<sol[i]<<' ';
        out<<'\n';
    }
    else out<<"-1\n";
    in.close();
    out.close();
    return 0;
}