Pagini recente » Cod sursa (job #2967617) | Cod sursa (job #57613) | Cod sursa (job #2739601) | Cod sursa (job #1767304) | Cod sursa (job #723603)
Cod sursa(job #723603)
#include <fstream>
#include <set>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
long TE[100005] = {0};
long From[500005] = {0};
long To[500005] = {0};
long Taken[500005] = {0};
//set<long> M[100001];
set<long> *M;
int main(void)
{
fstream fin("ciclueuler.in",ios::in);
fstream fout("ciclueuler.out",ios::out);
long Noduri,Muchii,i,a,b;
M = new set<long>[100001];
fin >> Noduri >> Muchii;
for (i = 0;i < Muchii;i += 1)
{
fin >> a >> b;
TE[a] += 2;
TE[b] += 2;
From[i] = a;
To[i] = b;
Taken[i] = 0;
M[a].insert(i);
M[b].insert(i);
}
vector<long> V;
stack<long> S;
queue<long> Q;
Q.push(1);
TE[1] |= 1;
while (Q.empty() == false)
{
i = Q.front();
Q.pop();
for (set<long>::iterator it = M[i].begin();it != M[i].end();it++)
{
if ((TE[To[*it]] & 1) == 0)
{
Q.push(To[*it]);
TE[To[*it]] |= 1;
}
if ((TE[From[*it]] & 1) == 0)
{
Q.push(From[*it]);
TE[From[*it]] |= 1;
}
}
}
for (i = 1;i <= Noduri;i += 1)
{
if ((TE[i] & 3) != 1)
{
fout << "-1";
fin.close();
fout.close();
return 0;
}
}
S.push(1);
while (S.empty() == false)
{
a = S.top();
if (M[a].empty() == true)
{
V.push_back(a);
S.pop();
continue;
}
i = *M[a].begin();
M[To[i]].erase(i);
M[From[i]].erase(i);
if (From[i] == a)
{
S.push(To[i]);
}
else
{
S.push(From[i]);
}
}
for (i = (V.size() - 1);i > 0;i -= 1)
{
fout << V[i] << " ";
}
fin.close();
fout.close();
return 0;
}