Pagini recente » Cod sursa (job #2450816) | Cod sursa (job #2033053) | Cod sursa (job #1468084) | Cod sursa (job #1283434) | Cod sursa (job #2422866)
#include <fstream>
#include <vector>
#include <bitset>
#include <tuple>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
const int MaxN = 100001;
const int MaxE = 500001;
using IT = vector<tuple<int, int>>::iterator;
using VIT = vector<IT>;
bitset<MaxE> v;
vector<vector<tuple<int, int>>> G;
vector<int> ce;
int n, m;
void CitesteGraf();
void AfiseazaCiclu();
bool EsteEulerian();
void DeterminaCiclu(int x);
int main()
{
CitesteGraf();
if(!EsteEulerian())
fout << "-1";
else
{
DeterminaCiclu(1);
AfiseazaCiclu();
}
}
void CitesteGraf()
{
fin >> n >> m;
G = vector<vector<tuple<int, int>>>(n + 1);
// E = vector<Edge> (m + 1);
int a, b;
for(int i = 1; i <= m; ++i)
{
fin >> a >> b;
G[a].emplace_back(b, i);
G[b].emplace_back(a, i);
}
}
bool EsteEulerian()
{
for(int x = 1; x <= n; ++x)
if(G[x].size() % 2 == 1)
return false;
return true;
}
void DeterminaCiclu(int x)
{
VIT p = VIT(n + 1);
for(int i = 1; i <= n; ++i)
p[i] = G[i].begin();
int y, e;
stack<int> stk;
stk.push(1);
while(!stk.empty())
{
x = stk.top();
if(p[x] == G[x].end())
{
ce.emplace_back(x);
stk.pop();
}
else
{
while(p[x] != G[x].end())
{
tie(y, e) = *p[x]++;
if(v[e])
continue;
v[e] = 1;
stk.push(y);
break;
}
}
}
}
void AfiseazaCiclu()
{
for(size_t i = 0; i < ce.size() - 1; ++i)
fout << ce[i] << ' ';
}