Pagini recente » Cod sursa (job #1141773) | Cod sursa (job #779091) | Cod sursa (job #2459099) | Cod sursa (job #3159321) | Cod sursa (job #2055493)
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int nmax = 100000;
struct Edge {
int to;
int rev;
bool del;
};
vector<Edge> g[1 + nmax];
bool mark[1 + nmax];
int start, n, m;
vector<int> sol;
void addedge(int i, int j) {
int loop = 0;
if(i == j)
loop = 1;
Edge direct = {j, g[j].size() + loop, false};
Edge inverse = {i, g[i].size(), false};
g[i].push_back(direct);
g[j].push_back(inverse);
start = i;
}
void bfs() {
queue < int > q;
mark[start] = true;
q.push(start);
while(!q.empty()){
int from = q.front();
q.pop();
for(int i = 0; i < g[from].size(); i++){
Edge &e = g[from][i];
if(mark[e.to] == false){
mark[e.to] = true;
q.push(e.to);
}
}
}
}
void eulercircuit(int from) {
stack < int > st;
st.push(from);
while(!st.empty()){
int from = st.top();
if(0 < g[from].size()) {
Edge e = {g[from].back().to, g[from].back().rev, g[from].back().del};
g[from].pop_back();
if(e.del == false) {
g[e.to][e.rev].del = true;
st.push(e.to);
}
} else {
sol.push_back(from);
st.pop();
}
}
}
int main() {
in >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
in >> x >> y;
addedge(x, y);
}
bfs();
bool hassol = true;
for(int i = 1; i <= n; i++){
if(0 < g[i].size()){
if(mark[i] == false || g[i].size() % 2 == 1)
hassol = false;
}
}
if(hassol == true) {
eulercircuit(1);
for(int i = sol.size()-1; 0 < i; i--)
out << sol[i] << " ";
} else {
out << "-1\n";
}
return 0;
}