Pagini recente » Cod sursa (job #2629231) | Cod sursa (job #1933069) | Cod sursa (job #1442809) | Cod sursa (job #674665) | Cod sursa (job #735607)
Cod sursa(job #735607)
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;
#define nmax 100010
#define pb push_back
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
vector<int> graph[nmax];
vector<int> solution;
int n,m,x,y;
void read_input()
{
in>>n>>m;
for(int i=0;i<m;i++)
{
in>>x>>y;
graph[x].pb(y);
graph[y].pb(x);
}
}
bool Eulerian()
{
for(int i=1;i<=n;i++) if(graph[i].size()%2) return false;
return true;
}
void euler(int start)
{
stack <int> s;
s.push(start);
while(!s.empty())
{
int node=s.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());
s.push(nextNode);
node=nextNode;
}
solution.pb(s.top());
s.pop();
}
solution.pop_back();
for(vector<int>::iterator it=solution.begin();it!=solution.end();++it) out<<*it<<" ";
out<<"\n";
}
int main()
{
int i;
read_input();
if(Eulerian()==true) euler(1);
else out<<-1<<"\n";
in.close();
out.close();
return 0;
}