Cod sursa(job #2660433)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 19 octombrie 2020 13:27:24
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;


ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector<pair<int,int>>graf[100005];
vector<int> viz;
vector<int>ciclu;

void dfs(int nod)
{
	stack<int> st;
	st.push(nod);
	while(!st.empty())
	{
		nod=st.top();
		if(!graf[nod].empty())
		{
			while(!graf[nod].empty())
			{
				pair<int,int> var=graf[nod].back();
				if(!viz[var.second])
				{
					viz[var.second]=1;
					graf[nod].pop_back();
					st.push(var.first);
					break;
				}
				else
					graf[nod].pop_back();
			}
		}
		else
		{
			ciclu.push_back(nod);
			st.pop();
		}
	}
}
int main()
{
	int n,m;
	in>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		in>>x>>y;
		viz.push_back(0);
		graf[x].push_back({y,i-1});
		graf[y].push_back({x,i-1});
	}
	for(int i=1;i<=n;i++)
		if(graf[i].size()%2==1)
		{
			out<<"-1";
			return 0;
		}

	dfs(1);
	if(ciclu.size()<=m)
		out<<"-1";
	else 
		for(int i=0;i<ciclu.size();i++)
			out<<ciclu[i]<<" ";

	return 0;
	return 0;
}