Pagini recente » Cod sursa (job #1144934) | Cod sursa (job #1932062) | Cod sursa (job #286467) | Cod sursa (job #439516) | Cod sursa (job #1492730)
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
#include <map>
using namespace std;
vector<int> No[100001];
int gr[100001];
map<pair<int, int>,bool> del;
vector<int> cicle;
ifstream f("ciclueuler.in");
ofstream of("ciclueuler.out");
void euler(int root){
stack<int> s;
pair<int, int>p;
s.push(root);
while (!s.empty()){
int x = s.top();
while (No[x].size() > 0 && del[make_pair(x, No[x].back())] == 1){
del[make_pair(x, No[x].back())] = 0;
No[x].pop_back();
}
if (No[x].size() > 0){
int c = No[x].back();
No[x].pop_back();
s.push(c);
del[make_pair(c, x)] = 1;
//No[c].erase(find(No[c].begin(), No[c].end(), x));
}
else{
cicle.push_back(x);
s.pop();
}
}
}
int main(){
int N, M, a, b;
string s;
getline(f,s);
int nr, j;
nr = 0;
j = 0;
while (s[j] != ' '){
nr = nr * 10 + s[j] - '0';
++j;
}
N = nr;
++j;
nr = 0;
while (j<s.size()){
nr = nr * 10 + s[j] - '0';
++j;
}
M = nr;
for (int i = 0; i < M; ++i){
getline(f, s);
nr = 0;
j = 0;
while (s[j] !=' '){
nr = nr * 10 + s[j]-'0';
++j;
}
a = nr;
++j;
nr = 0;
while (j<s.size()){
nr = nr * 10 + s[j] - '0';
++j;
}
b = nr;
No[a].push_back(b);
No[b].push_back(a);
++gr[a]; ++gr[b];
del[make_pair(a, b)] = 0;
del[make_pair(b, a)] = 0;
}
for (int i = 1; i <= N; ++i)
if (gr[i] % 2 == 1) {
of << -1; return 0;
}
euler(1);
for (int i = 0; i < cicle.size() - 1; ++i)
of << cicle[i] << " ";
}