Cod sursa(job #2473626)

Utilizator gabbie02Thomits Gabriel gabbie02 Data 13 octombrie 2019 22:07:22
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <set>
#include <stack>

using namespace std;

ofstream fout("ciclueuler.out");
multiset<unsigned int> adjlist[100001];
unsigned int v;

bool isEuler()
{
    ifstream fin("ciclueuler.in");
	unsigned int i, j;
	fin >> v >> i;
	while(fin >> i >> j){
		adjlist[i].insert(j);
		adjlist[j].insert(i);
	}
	fin.close();
	for(i = 1; i <= v; i++){
		if(adjlist[i].size() & 1){
			return false;
		}
	}
	return true;
}

int main()
{
    stack<unsigned int> nodes;
    stack<unsigned int> cycle;
    unsigned int i, j;
	if(isEuler()){
        nodes.push(1);
        while(!nodes.empty()){
            i = nodes.top();
            if(adjlist[i].size()){
                j = *adjlist[i].begin();
                adjlist[j].erase(adjlist[j].find(i));
                adjlist[i].erase(adjlist[i].begin());
                nodes.push(j);
            } else {
                cycle.push(nodes.top());
                nodes.pop();
            }
        }
        while(cycle.size() > 1){
            fout << cycle.top() << " ";
            cycle.pop();
        }
	} else {
		fout << -1;
	}
	return 0;
}