Pagini recente » Cod sursa (job #638998) | Cod sursa (job #1241457) | Cod sursa (job #2549951) | Cod sursa (job #1952341) | Cod sursa (job #963710)
Cod sursa(job #963710)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
vector <int> graf[100001];
int n , m;
int grad[100001];
vector <int> ciclu;
stack <int> S;
void read()
{
ifstream in("ciclueuler.in");
in >> n >> m;
for (int i = 0;i<m;i++)
{
int x , y;
in >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
grad[x]++;
grad[y]++;
}
}
bool este_euler()
{
for (int i = 1;i<=n;i++)
if (grad[i] % 2 != 0) return 0;
return 1;
}
void sterge(int x , int y)
{
grad[x]--;
grad[y]--;
graf[x].erase(graf[x].begin());
vector<int>::iterator it;
for (it = graf[y].begin();it!=graf[y].end();it++)
{
if (*it == x)
{
graf[y].erase(it);
break;
}
}
}
void parcurgere()
{
int nod = 1;
do
{
int v = nod;
while(true)
{
if (graf[v].empty()) break;
int w = graf[v].front();
sterge(v,w);
S.push(v);
v = w;
}
nod = S.top();
S.pop();
ciclu.push_back(v);
}while(!S.empty());
}
int main()
{
ofstream out("ciclueuler.out");
read();
if (este_euler())
{
parcurgere();
for (int i =0;i<ciclu.size();i++)
out << ciclu[i] << " ";
}
else
{
out << "-1";
}
return 0;
}