Cod sursa(job #963710)

Utilizator Aida_SilviaStrimbeanu Aida Silvia Aida_Silvia Data 18 iunie 2013 14:19:33
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

vector <int> graf[100001];
int n , m;
int grad[100001];
vector <int> ciclu;
stack <int> S;


void read()
{
    ifstream in("ciclueuler.in");
    in >> n >> m;
    for (int i = 0;i<m;i++)
    {
        int x , y;
        in >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
        grad[x]++;
        grad[y]++;
    }
}

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

void sterge(int x , int y)
{
    grad[x]--;
    grad[y]--;
    graf[x].erase(graf[x].begin());
    vector<int>::iterator it;
    for (it = graf[y].begin();it!=graf[y].end();it++)
    {
        if (*it == x)
        {
            graf[y].erase(it);
            break;
        }
    }
}

void parcurgere()
{

    int nod = 1;
    do
    {
        int v = nod;
        while(true)
        {
            if (graf[v].empty()) break;
            int w = graf[v].front();
            sterge(v,w);
            S.push(v);
            v = w;
        }
        nod = S.top();
        S.pop();
        ciclu.push_back(v);

    }while(!S.empty());
}

int main()
{
    ofstream out("ciclueuler.out");
    read();
    if (este_euler())
    {
        parcurgere();
        for (int i =0;i<ciclu.size();i++)
            out << ciclu[i] << " ";
    }
    else
    {
        out << "-1";
    }
    return 0;
}