Pagini recente » Cod sursa (job #2920956) | Cod sursa (job #1619057)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream ka("ciclueuler.in");
ofstream ki("ciclueuler.out");
const int N_MAX = 100000;
const int M_MAX = 500000;
struct muchie
{
int index, id;
};
vector <muchie> graf[N_MAX + 1];
vector <int> sol;
stack <int> stiva;
bool folosita[M_MAX + 1];
int grad[N_MAX + 1], folosite;
int n, m, a, b;
int main()
{
ka >> n >> m;
for(int i = 1; i <= m; i++)
{
ka >> a >> b;
grad[a]++;
grad[b]++;
muchie mm;
mm.index = b;
mm.id = i;
graf[a].push_back(mm);
mm.index = a;
graf[b].push_back(mm);
}
bool eulerian = true;
for(int i = 1; i <= n && eulerian; i++)
if(grad[i] % 2 == 1)
eulerian = false;
if(eulerian)
{
int curent = 1;
while(curent < n && grad[curent] == 0)
curent++;
stiva.push(curent);
while(!stiva.empty())
{
int t = stiva.top();
while(!graf[t].empty() && folosita[graf[t].back().id])
graf[t].pop_back();
if(!graf[t].empty())
{
folosita[graf[t].back().id] = true;
folosite++;
stiva.push(graf[t].back().index);
graf[t].pop_back();
}
else
{
if(stiva.size() != 1)
sol.push_back(t);
stiva.pop();
}
}
}
if(folosite != m)
eulerian = false;
if(eulerian)
for(int i = 0; i < sol.size(); i++)
ki << sol[i] << " ";
else
ki << -1;
return 0;
}