Mai intai trebuie sa te autentifici.
Cod sursa(job #1689834)
Utilizator | Data | 14 aprilie 2016 16:42:35 | |
---|---|---|---|
Problema | Ciclu Eulerian | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.29 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100003
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector<int> vec[MAX];
vector<int> ciclu;
void del(int a, int b) {
for(vector<int>::iterator it = vec[a].begin(); it != vec[a].end(); it++) {
if(*it == b) {
vec[a].erase(it);
return;
}
}
}
void euler() {
stack<int> st;
st.push(1);
vector<int>::iterator it;
int nod;
int nxt;
while(!st.empty()) {
nod = st.top();
if(vec[nod].size() != 0) {
nxt = vec[nod].front();
del(nod, nxt);
del(nxt, nod);
st.push(nxt);
} else {
ciclu.push_back(nod);
st.pop();
}
}
}
int main() {
int n,m,a,b;
in >> n >> m;
for(int i = 1; i <= m; i++) {
in >> a >> b;
vec[a].push_back(b);
vec[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
if(vec[i].size()%2 != 0) {
out << "-1";
return 0;
}
}
euler();
for(vector<int>::iterator it = ciclu.begin(); it != ciclu.end(); it++)
out << *it << " ";
return 0;
}