Cod sursa(job #876942)

Utilizator TeOOOVoina Teodora TeOOO Data 12 februarie 2013 13:24:28
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

//Definitii

//Constanta
const int sz = (int)1e5+1;

//Functii
void euler(int startNode);
bool eulerian();

// Variabile
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");

bool visited[sz];
int nodes, edges;
vector <int> graph[sz], answer;

// Main
int main()
{
    in >> nodes >> edges;

    int rFrom, rTo;
    while(edges--)
    {
        in >> rFrom >> rTo;
        graph[rFrom].push_back(rTo);
        graph[rTo].push_back(rFrom);
    }

    if(!eulerian())
        out << "-1";
    else
    {
        euler(1);
        answer.pop_back();
        vector <int>::iterator it, end = answer.end();
        for(it=answer.begin(); it!=end; ++it)
           out << *it << ' ';
    }

    in.close();
    out.close();
    return 0;
}

bool eulerian()
{
    for(int i=1; i<=nodes; ++i)
        if(graph[i].size()&1)
            return false;
    return true;
}

void euler(int startNode)
{
    stack<int> st;
    st.push(startNode);

    while(!st.empty())
    {
        int node = st.top();
        while(!graph[node].empty())
        {
            int nextNode = *graph[node].begin();
            graph[nextNode].erase(find(graph[nextNode].begin(), graph[nextNode].end(), node));
            graph[node].erase(graph[node].begin());

            st.push(nextNode);
            node = nextNode;
        }
        answer.push_back(node);
        st.pop();
    }
}