Cod sursa(job #1461324)

Utilizator RobertSSamoilescu Robert RobertS Data 15 iulie 2015 14:01:03
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <vector>
using namespace std;

#define MAX 100005

/*fisiere de intrare respectiv iesire*/
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");


/*lista de adiacenta*/
vector<int> graf[MAX];

/*gradul fiecarui nod*/
int grad[MAX];
/*vector de noduri vizitate*/
bool vizitat[MAX];


/*functie de eliminare a unui element dintr-o lista de adiacenta*/
bool EraseElement(vector<int> &v, int elem)
{
    vector<int>::iterator it;
    for(it = v.begin(); it != v.end(); it++)
    {
        if(*it == elem)
            break;
    }

    if(it != v.end())
    {
        v.erase(it);
        return true;
    }

    return false;
}


int n, m; /*numarul de noduri, respectiv numarul de laturi*/

/*Functie de citrire*/
void Citire()
{

    fin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int nod1, nod2;
        fin >> nod1 >> nod2;
       // cout << nod1 << " " << nod2 << endl;
        graf[nod1].push_back(nod2);
        graf[nod2].push_back(nod1);
        grad[nod1]++; grad[nod2]++;
    }
}


void DFS(int nod)
{
    vizitat[nod] = true;
    for(vector<int>::iterator it = graf[nod].begin(); it != graf[nod].end(); it++)
    {
        if(!vizitat[*it])
            DFS(*it);

    }
}

void Euler(int nod)
{
    while(!graf[nod].empty())
    {
        int adiacent = graf[nod].front();
        EraseElement(graf[nod], adiacent);
        EraseElement(graf[adiacent], nod);

        Euler(adiacent);
    }

    fout << nod << " ";
}

bool Verificare()
{
    for(int i = 1; i <= n; i++)
    {
        if(!vizitat[i] || grad[i] % 2 != 0) return false;
    }

    return true;
}

int main()
{
    Citire();
    DFS(1);
    if(Verificare())
    {
        Euler(1);
        fout << '\n';
    }
    else
        fout << "-1\n";





    return 0;
}