Cod sursa(job #2568816)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 4 martie 2020 10:02:21
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda r3capitusulare Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e5 + 1;

vector <pair <int, int> > adj[DIM];
bitset <DIM * 5> vis;
vector <int> ans;

void dfs(int nod)
{
	while(true)
	{
		if(adj[nod].size() == 0)
		{
			ans.emplace_back(nod);
			return ;
		}
		else
		{
			int id = adj[nod].back().second;
			int x = adj[nod].back().first;
			
			adj[nod].pop_back();
			
			if(vis[id] == true)
				continue;
			
			vis[id] = 1;
			dfs(x);
		}
	}
}

main()
{
	int n, m;
	fin >> n >> m;
	
	for(; m; --m)
	{
		int x, y;
		fin >> x >> y;
		
		adj[x].emplace_back(y, m);
		adj[y].emplace_back(x, m);
	}
	
	for(int i = 1; i <= n; ++i)
		if(adj[i].size() % 2 == 1)
		{
			fout << -1 << '\n';
			return 0;
		}
	
	dfs(1);
	
	ans.pop_back();
	
	for(auto i : ans)
		fout << i << ' ';
}