Cod sursa(job #1409837)

Utilizator cautionPopescu Teodor caution Data 30 martie 2015 18:57:12
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <list>
#include <vector>
#include <stack>
using namespace std;
long n, m;
list<long> *graf;
vector<long> ciclu;
bool isEuler()
{
    for(long i=1; i<=n; ++i)
        if(graf[i].size()%2==1||graf[i].size()==0) return false;
    return true;
}
void buildEuler()
{
    long a, b;
    stack<long> s;
    s.push(1);
    while(!s.empty())
    {
        a=s.top();
        if(graf[a].size())
        {
            b=graf[a].front();
            for(list<long>::iterator it=graf[b].begin(), ed=graf[b].end(); it!=ed; ++it)
                if(*it==a)
                {
                    graf[b].erase(it);
                    break;
                }
            graf[a].pop_front();
            s.push(b);
        }
        else
        {
            ciclu.push_back(a);
            s.pop();
        }
    }
}
int main()
{
    ifstream in("ciclueuler.in");
    ofstream out("ciclueuler.out");
    long a, b;
    in>>n>>m;
    graf = new list<long>[n+1];
    for(long i=0; i<m; ++i)
    {
        in>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    if(isEuler())
    {
        buildEuler();
        for(vector<long>::iterator it=ciclu.begin(), ed=ciclu.end(); it!=ed; ++it)
            out<<*it<<' ';
    }
    else
        out<<"-1\n";
    return 0;
}