Pagini recente » Cod sursa (job #1011351) | Cod sursa (job #3000337) | Cod sursa (job #308104) | Poze preONI 2007 - pregatiri | Cod sursa (job #876942)
Cod sursa(job #876942)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
//Definitii
//Constanta
const int sz = (int)1e5+1;
//Functii
void euler(int startNode);
bool eulerian();
// Variabile
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
bool visited[sz];
int nodes, edges;
vector <int> graph[sz], answer;
// Main
int main()
{
in >> nodes >> edges;
int rFrom, rTo;
while(edges--)
{
in >> rFrom >> rTo;
graph[rFrom].push_back(rTo);
graph[rTo].push_back(rFrom);
}
if(!eulerian())
out << "-1";
else
{
euler(1);
answer.pop_back();
vector <int>::iterator it, end = answer.end();
for(it=answer.begin(); it!=end; ++it)
out << *it << ' ';
}
in.close();
out.close();
return 0;
}
bool eulerian()
{
for(int i=1; i<=nodes; ++i)
if(graph[i].size()&1)
return false;
return true;
}
void euler(int startNode)
{
stack<int> st;
st.push(startNode);
while(!st.empty())
{
int node = st.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());
st.push(nextNode);
node = nextNode;
}
answer.push_back(node);
st.pop();
}
}