Cod sursa(job #1204676)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 3 iulie 2014 17:00:05
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
using namespace std;
#include <fstream>
#include <vector>
#include <stack>
ofstream fout("ciclueuler.out");
const int Nmax = 100000;

int m, n;
vector<int> v[Nmax+1];
vector<int> sol;
int deg[Nmax+1];
bool uz[Nmax+1];
stack<int> S;

void read() ;
int DFS(int) ;
int esteEulerian() ;
void creareLant(int) ;

int main()
{
    read();
    if( !esteEulerian() ) {fout << "-1\n"; return 0;}
    S.push(1);
    while( !S.empty() )
    {
        creareLant(S.top());
        sol.push_back(S.top());
        S.pop();
    }
    vector<int>::iterator it = sol.begin(); ++it;
    for(; it != sol.end(); ++it)
        fout << *it << ' ';
    fout << '\n';
    return 0;
}


void read()
{
    ifstream fin("ciclueuler.in");
    int a, b;
    fin >> n >> m;
    for(; m; --m)
    {
        fin >> a >> b;
        ++deg[a]; ++deg[b];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    fin.close();
}


int DFS(int vf)
{
    int nr = 1, ok; uz[vf] = 1;
    vector<int>::iterator it;
    for(S.push(vf); !S.empty(); )
    {
        vf = S.top(); ok = 0;
        for(it = v[vf].begin(); it != v[vf].end() && !ok; ++it)
            if(!uz[*it])
            {
                S.push(*it);
                uz[*it] = 1; ok = 1; ++nr;
            }
        if(!ok) S.pop();
    }
    return nr == n;
}


int esteEulerian()
{
    if(!DFS(1)) return 0;
    for(int i = 1; i <= n; ++i)
        if(deg[i] & 1) return 0;
    return 1;
}


void creareLant(int vf)
{
    int nod;
    vector<int>::iterator it;
    while(deg[vf])
    {
        nod = *(v[vf].begin());
        S.push(nod);
        v[vf].erase(v[vf].begin());
        for(it = v[nod].begin(); *it != vf; ++it) ;v[nod].erase(it);
        --deg[vf]; --deg[nod];
        vf = nod;
    }
}