Pagini recente » Cod sursa (job #2653425) | Cod sursa (job #1239060) | Cod sursa (job #3177217) | Cod sursa (job #840033) | Cod sursa (job #1131600)
#include <fstream>
#include <stack>
#include <vector>
#define vintp vector<pair<int,int> >::iterator
using namespace std;
ifstream fin ("ciclueuler.in");
ofstream fout ("ciclueuler.out");
int n,m,t,a,b;
int deg[100001];
bool viz[100001];
bool v[500001];
int E[500001];
vector <pair<int,int > > G[100001];
stack <int> S;
void dfs (int x)
{
viz[x] = 1;
for (vintp it = G[x].begin (); it != G[x].end(); ++it)
{
if (!viz[it->first])
dfs (it->first);
}
}
bool eulerian ()
{
dfs (1);
for (int i=1; i<=n; ++i)
{
if ((!viz[i] && deg[i]) || deg[i] % 2 != 0)
return 0;
}
return 1;
}
int main()
{
fin>>n>>m;
for (int i=1; i<=m; ++i)
{
fin>>a>>b;
G[a].push_back (make_pair(b,i));
G[b].push_back (make_pair(a,i));
++deg[a];
++deg[b];
}
if (!eulerian ())
{
fout<<-1;
return 0;
}
for (int i=1; i<=n; ++i)
{
if (deg[i])
{
S.push(i);
break;
}
}
while (!S.empty ())
{
int x = S.top ();
if (G[x].empty ())
{
E[++t] = x;
S.pop ();
}
else
while (!G[x].empty())
{
int y = G[x][G[x].size()-1].first;
if (!v[G[x][G[x].size()-1].second])
{
v[G[x][G[x].size()-1].second] = 1;
G[x].pop_back ();
S.push (y);
break;
}
else G[x].pop_back ();
}
}
for (int i=1; i<=t-1; ++i)
fout<<E[i]<<" ";
}