Cod sursa(job #2868096)

Utilizator Madalin_IonutFocsa Ionut-Madalin Madalin_Ionut Data 10 martie 2022 18:42:41
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

int n, m, viz[500003], sol[500003], g[100003], p;
int st[500003], dr[500003];
unsigned int poz[100003];
vector<int> h[100003];

void Grad()
{
	int i;
	for (i = 1; i <= n; i++)
		g[i] = h[i].size();
}

int ToatePare()
{
	for (int i = 1; i <= n; i++)
		if (g[i] & 1) return 0;
	return 1;
}

void Euler(int k)
{
	int i;
	while (poz[k] < h[k].size())
	{
		i = h[k][poz[k]];
		poz[k]++;
		if (viz[i] == 0)
		{
			viz[i] = 1;
			Euler(st[i] + dr[i] - k);
		}
	}
	sol[++p] = k;
}

void Afis()
{
	int i;
	for (i = 1; i <= p; i++)
		fout << sol[i] << " ";
}

int main()
{
	int i;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> st[i] >> dr[i];
		h[st[i]].push_back(i);
		h[dr[i]].push_back(i);
	}
	Grad();
	if (ToatePare() == 0) fout << "-1\n";
	else
	{
		Euler(1);
		Afis();
	}
	fout.close();
}