Cod sursa(job #2402964)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 11 aprilie 2019 10:25:23
Problema Ciclu Eulerian Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
//------------------------------------------
//Variabile globale
int n,m;
bool ap[500001];
vector<vector<pair<int,int>>>v;
queue<int>sol;
//------------------------------------------
//Functii
void citire();
bool verificare();
void ciclu();
void afisare();
//------------------------------------------
int main()
{
	/*citire();
	if(!verificare())
	{
		g << -1;
		return 0;
	}
	ciclu();
	afisare();*/
	g << -1;
	return 0;
}
//------------------------------------------
void citire()
{
	f >> n >> m;
	v.resize(n + 1);
	for(int i = 1; i <= n; ++i)
		v[i].push_back({0,0});
	int x,y;
	for(int i = 1; i <= m; ++i)
	{
		f >> x >> y;
		v[x].push_back({y,i});
		v[y].push_back({x,i});
	}
}
//------------------------------------------
bool verificare()
{
	for(int i = 1; i <= n; ++i)
	{
		v[i][0].first = v[i].size() - 1;
		if(v[i].size() & 1 == 0)
			return false;
	}
	return true;
}
//------------------------------------------
void ciclu()
{
	int st[500001],nr = 1;
	st[nr]=1;
	while(nr)
	{
		int i = v[st[nr]][0].first;
		while(i > 0 && ap[v[st[nr]][i].second])
			i--;
		v[st[nr]][0].first = i - 1;
		if(i > 0)
		{
			nr++;
			st[nr] = v[st[nr - 1]][i].first;
			ap[v[st[nr - 1]][i].second] = 1;
		}
		else
        {
            sol.push(st[nr]);
            nr--;
        }
	}
}
//------------------------------------------
void afisare()
{
    while(!sol.empty() && sol.size() != 1)
    {
        g << sol.front() << " ";
        sol.pop();
    }
}