Pagini recente » Cod sursa (job #2584096) | Cod sursa (job #2428641) | Cod sursa (job #786212) | Cod sursa (job #160702) | Cod sursa (job #672369)
Cod sursa(job #672369)
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MAXSIZE = 100001;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int nodes,edges;
vector<int> graph[MAXSIZE];
stack<int> stk;
vector<int> solution;
void euler(int node);
bool hasEulerianCycle();
int main() {
in >> nodes >> edges;
int from,to;
for(int i=1;i<=edges;i++) {
in >> from >> to;
graph[from].push_back(to);
graph[to].push_back(from);
}
if(!hasEulerianCycle())
out << "-1\n";
else {
euler(1);
solution.pop_back();
for(vector<int>::iterator it=solution.begin();it!=solution.end();++it)
out << *it << " ";
out << "\n";
}
return (0);
}
void euler(int startNode) {
stk.push(startNode);
while(!stk.empty()) {
int node = stk.top();
while(!graph[node].empty()) {
int nextNode = *graph[node].begin();
graph[nextNode].erase(find(graph[nextNode].begin(),graph[nextNode].end(),node));
graph[node].erase(graph[node].begin());
stk.push(nextNode);
node = nextNode;
}
solution.push_back(stk.top());
stk.pop();
}
}
bool hasEulerianCycle() {
for(int i=1;i<=nodes;i++)
if((graph[i].size() %2))
return false;
return true;
}