Cod sursa(job #671261)

Utilizator psycho21rAbabab psycho21r Data 31 ianuarie 2012 00:02:08
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <list>
#include <stack>

using namespace std;

list <int> graph[100010];

int main()
{
    int n, m;
    ifstream in("ciclueuler.in");
    in >> n >> m;
    for(int a,b;m;--m)
    {
        in >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    in.close();
    ofstream out("ciclueuler.out");
    for(int i = 1; i <= n; ++i)
    {
        if(graph[i].size()&1)
        {
            out << "-1";
            return 0;
        }
    }
    int v = 1;
    list<int> L;
    stack<int> S;
    do
    {
        while(!graph[v].empty())
        {
            int w = graph[v].front();
            graph[v].pop_front();
            S.push(v);
            for(list<int>::iterator it=graph[w].begin(); it!=graph[w].end(); ++it)
            {
                if(*it==v)
                {
                    graph[w].erase(it);
                    break;
                }
            }
            v = w;
        }
        v = S.top();
        S.pop();
        L.push_front(v);
    }
    while(!S.empty());

    for(list<int>::iterator it=L.begin(); it!=L.end(); ++it)
    {
        out << *it << " ";
    }
    out.close();

    return 0;
}