Cod sursa(job #2865246)

Utilizator alextmAlexandru Toma alextm Data 8 martie 2022 17:28:40
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5;

vector<pair<int,int>> G[MAXN];
bool viz[MAXN];
int n, m;

bool isEuler() {
	int ok = 1;
	for(int j = 1; j <= n; j++)
		if(G[j].size() % 2 == 1)
			ok = 0;
	return ok;
}

int main() {
	ifstream cin("ciclueuler.in");
	ofstream cout("ciclueuler.out");
	
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		G[x].emplace_back(y, i);
		G[y].emplace_back(x, i);
	}
	
	if(!isEuler()) {
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	
	vector<int> ans;
	stack<int> st;
	st.push(1);
	
	while(!st.empty()) {
		int node = st.top();
		if(G[node].size()) {
			int x = G[node].back().first;
			int edge = G[node].back().second;
			G[node].pop_back();
			
			if(viz[edge] == 0) {
				viz[edge] = 1;
				st.push(x);
			}
		} else {
			st.pop();
			ans.push_back(node);
		}
	}
	
	for(int node : ans)
		cout << node << ' ';
	cout << '\n';
	
	return 0;
}