Cod sursa(job #1605769)

Utilizator dianaorasanuDiana Orasanu dianaorasanu Data 19 februarie 2016 14:51:18
Problema Ciclu Eulerian Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>

#define NMAX 100010
#define MAX 500010

using namespace std;

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

void euler(int x);
void DFS(int x);
void sterge(int p, int x);
void adauga(int x);

vector <int> M[NMAX];

int n, m, i, el, sol[2*MAX], x, y;
bool v[NMAX];

int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        M[x].push_back(y);
        M[y].push_back(x);
    }
    DFS(1);
    for(i = 1; i <= n; ++i)
        if(M[i].size() % 2 != 0 || v[i] != true)
    {
        fout << "-1\n";
        return 0;
    }
    euler(1);
    sol[0]=1;
    for(i = 0; i < el; ++i)
        fout << sol[i] << ' ';
    return 0;
}

void euler(int x)
{
    int i;
    int p;
    while(!M[x].empty())
    {
        p = M[x].back();
        sterge(p, x);
        M[x].pop_back();
        euler(p);
        adauga(x);
    }
}

void sterge(int p, int x)
{
    int i;
    for(i = 0; i < M[p].size(); ++i)
        if(M[p][i] == x)
    {
        swap(M[p][i], M[p][M[p].size()-1]);
        M[p].pop_back();
        break;///daca sunt muchii care se repeta?
    }

}
void adauga(int x)
{
    ++el;
    sol[el] = x;
}

void DFS(int x)
{
    int i;
    for(i = 0; i < M[x].size(); ++i)
    {
        if(v[M[x][i]] == false)
        {
            v[M[x][i]] = true;
            DFS(M[x][i]);
        }
    }
}