Pagini recente » Cod sursa (job #1118928) | Cod sursa (job #1183872) | Cod sursa (job #1597235) | Cod sursa (job #876943)
Cod sursa(job #876943)
// Include
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
// Definitii
#define pb push_back
#define popb pop_back
// Constante
const int sz = (int)1e5+1;
// Functii
bool eulerian();
void euler();
// Variabile
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
bool visited[sz];
int nodes, edges;
vector<int> graph[sz];
vector<int> answer;
// Main
int main()
{
in >> nodes >> edges;
int rFrom, rTo;
while(edges--)
{
in >> rFrom >> rTo;
graph[rFrom].pb(rTo);
graph[rTo].pb(rFrom);
}
if(!eulerian())
{
out << "-1\n";
in.close();
out.close();
return 0;
}
euler();
vector<int>::iterator it, end=answer.end();
for(it=answer.begin() ; it!=end ; ++it)
out << *it << ' ';
in.close();
out.close();
return 0;
}
void euler()
{
stack<int> st;
st.push(1);
while(!st.empty())
{
int current = st.top();
while(!graph[current].empty())
{
int nextNode = *graph[current].begin();
graph[nextNode].erase(find(graph[nextNode].begin(), graph[nextNode].end(), current));
graph[current].erase(graph[current].begin());
st.push(nextNode);
current = nextNode;
}
answer.pb(current);
st.pop();
}
answer.popb();
}
bool eulerian()
{
for(int i=1 ; i<=nodes ; ++i)
if(graph[i].size()&1)
return false;
return true;
}