Cod sursa(job #2049346)

Utilizator rangal3Tudor Anastasiei rangal3 Data 27 octombrie 2017 08:52:50
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
#define file "ciclueuler"
#define N 100003

using namespace std;

ifstream fin(file".in");
ofstream fout(file".out");

vector< vector<int> > v(N);

int n,m,x,y;
int gr[N];

bool Ciclu()
{
    for(int i=1; i<=n; ++i)
        if(gr[i] == 0 || gr[i]%2 != 0) return 0;
    return 1;
}

vector<int>::iterator it;

int sol[5*N],nsol;

inline void Euler(int nod)
{
    for(it = v[nod].begin(); it!=v[nod].end(); ++it)
    {
        int nodurm = *it;
        v[nod].erase(it);
        Euler(nodurm);

        sol[++nsol] = nod;
    }
}

int main()
{

    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        ++gr[x];
        ++gr[y];
    }

    if(Ciclu())
    {
        Euler(1);

        for(int i=1; i<=nsol; ++i)
            fout<<sol[i]<<" ";
    }
    else fout<<"-1\n";

    fin.close(); fout.close();
    return 0;
}