Pagini recente » Cod sursa (job #1405388) | Cod sursa (job #1783455) | Cod sursa (job #1676781) | Cod sursa (job #846038) | Cod sursa (job #3259242)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
struct muchie{
int x, y;
};
const int nmax = 100001, mmax=5e5 + 1;
vector<int> G[nmax];
muchie edges[mmax];
vector<int> rez;
bool deleted[mmax];
int getNextNode(int node)
{
while(!G[node].empty() && deleted[G[node].back()])
G[node].pop_back();
if(G[node].empty())
return 0;
int edgeId = G[node].back();
deleted[edgeId] = 1;
return edges[edgeId].x + edges[edgeId].y - node;
}
void euler(int nod)
{
while(int vecin = getNextNode(nod))
{
euler(vecin);
}
rez.push_back(nod);
}
int main()
{
int n, m;
fin >> n >> m;
for(int i=1; i<=m; i++)
{
int x, y;
fin >> x >> y;
edges[i]={x, y};
G[x].push_back(i);
G[y].push_back(i);
}
bool is_euler = 1;
for(int i=1; i<=n; i++)
is_euler = is_euler && (G[nmax].size()%2 == 0);
if(!is_euler)
{
fout << -1;
return 0;
}
euler(1);
for(vector<int>::iterator it=rez.begin(); it<rez.end()-1; it++)
fout << *it << ' ';
return 0;
}