Pagini recente » Cod sursa (job #518372) | Cod sursa (job #1129616) | Cod sursa (job #1880955) | Cod sursa (job #1799721) | Cod sursa (job #2055408)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#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;
};
int n, m, start;
bool mark[1 + NMAX];
vector < Edge > g[1 + NMAX];
vector < int > sol;
void addedge(int x, int y) {
int loop = 0;
if(x == y)
loop = 1;
Edge direct = {y, g[y].size() + loop, false};
Edge inverse = {x, g[x].size(), false};
g[x].push_back(direct);
g[y].push_back(inverse);
start = x;
}
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++) {
int to = g[from][i].to;
if(mark[to] == false) {
mark[to] = true;
q.push(to);
}
}
}
}
void read() {
in >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
in >> x >> y;
addedge(x, y);
}
}
void finalize() {
in.close();
out.close();
}
void eulercircuit(int start) {
stack < int > st;
st.push(start);
while(!st.empty()) {
int from = st.top();
int k = 0;
for(int i = 0; i < g[from].size(); i++) {
Edge &e = g[from][i];
if(e.del == false) {
k++;
e.del = true;
g[e.to][e.rev].del = true;
st.push(e.to);
break;
}
}
if(k == 0) {
sol.push_back(from);
st.pop();
}
}
}
void write() {
for(int i = sol.size() - 1; i > 0; i--) {
out << sol[i] << ' ';
}
}
void solve() {
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;
break;
}
}
}
if(hassol == true) {
eulercircuit(1);
write();
finalize();
} else {
out << "-1\n";
finalize();
exit(EXIT_SUCCESS);
}
}
int main()
{
read();
bfs();
solve();
return 0;
}