Pagini recente » Cod sursa (job #286846) | Cod sursa (job #387841) | Cod sursa (job #3126043) | Cod sursa (job #1582691) | Cod sursa (job #672084)
Cod sursa(job #672084)
// http://infoarena.ro/problema/ciclueuler
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXSIZE = 100001;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int nodes,edges;
vector<int> graph[MAXSIZE];
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);
}
inline void euler(int node) {
while(!graph[node].empty()) {
int nextNode = *graph[node].begin();
for(vector<int>::iterator it=graph[nextNode].begin();it!=graph[nextNode].end();++it)
if(*it == node) {
graph[nextNode].erase(it);
break;
}
graph[node].erase(graph[node].begin());
euler(nextNode);
}
solution.push_back(node);
}
bool hasEulerianCycle() {
for(int i=1;i<=nodes;i++)
if((graph[i].size() %2))
return false;
return true;
}