Pagini recente » Cod sursa (job #906284) | Cod sursa (job #279330) | Cod sursa (job #1798930) | Cod sursa (job #1159409) | Cod sursa (job #3334522)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX= 100'000;
const int MMAX = 500'000;
int N,M;
vector<pair<int,int>> G[NMAX +1];
//in graf avem lista de adiacenta + muchia asociata
ofstream fout("ciclueuler.out");
void ReadInput() {
ifstream fin("ciclueuler.in");
fin>>N>>M;
for(int i=1;i<=M;i++) {
int u,v;
fin>>u>>v;
G[u].push_back(make_pair(v,i));
G[v].push_back(make_pair(u,i));
}
fin.close();
}
bool visited[MMAX+1];
vector<int> ciclu_eulerian;
void FleuryAlgorithm(int nod) {
while (G[nod].size() > 0) {
auto [vecin, ind_muchie] = G[nod].back();
G[nod].pop_back();
if (visited[ind_muchie] == 1) continue;
visited[ind_muchie] = 1;
FleuryAlgorithm(vecin);
ciclu_eulerian.push_back(vecin);
}
}
void solveCicluEulerian() {
for (int i = 1; i <= M ;i++) {
visited[i] = 0;
}
ciclu_eulerian.clear();
FleuryAlgorithm(1);
bool single_connected_component = true;
for (int i = 1; i <= M; i++) {
if (visited[i] == 0) {
single_connected_component = false;
}
}
if (single_connected_component == false)
fout<<-1;
else {
for (int nod: ciclu_eulerian) {
fout<<nod<<" ";
}
}
}
int main() {
ReadInput();
bool grade_pare = true;
for (int i = 1; i <= N; i++) {
if (G[i].size() %2 != 0) {
grade_pare = false;
}
}
if (grade_pare == false) fout<<-1;
else solveCicluEulerian();
return 0;
}