Pagini recente » Cod sursa (job #1890342) | Cod sursa (job #2592972) | Cod sursa (job #2010075) | Cod sursa (job #61454) | Cod sursa (job #3327129)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#define NMAX 100002
#define MMAX 500002
using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
int n, m;
int nxt, nr;
int grad[NMAX];
bool gradeok = 1;
vector<vector<pair<int, int>>> graf;
bitset<MMAX>muchie; //muchie[i] = 1 daca a fost vizitat si 0 altfel
int unde[NMAX]; //unde[i]; unde am ramas cu verificarea muchiilor nodului i
queue<int> Q;
void citire();
void Euler(int nod);
int main()
{
int i, aux = 0;
citire();
Euler(1);
for(i = 1; i <= m; i++) aux += muchie[i];
for(i = 1; i <= n; i++)
if(grad[i] % 2 == 1 || grad[i] == 0)
gradeok = 0;
if(aux == m && gradeok) //am vizitat toate muchiile
{
while(!Q.empty())
{
fout<<Q.front()<<' '; Q.pop();
}
}
else
fout<<-1<<'\n';
return 0;
}
void Euler(int nod)
{
int i;
for(i = unde[nod]; i < graf[nod].size(); i++)
{
nxt = graf[nod][i].first;
nr = graf[nod][i].second;
if(!muchie[nr]) //daca nu am mai fost pe aceasta muchie
{
unde[nod] = i + 1;
muchie[nr] = 1;
Euler(nxt);
}
}
Q.push(nod);
}
void citire()
{
int i, x, y;
fin>>n>>m;
graf.resize(n + 2);
for(i = 1; i <= m; i++)
{
fin>>x>>y;
grad[x]++; grad[y]++;
graf[x].push_back({y, i});
graf[y].push_back({x, i});
}
}