Pagini recente » Cod sursa (job #1371104) | Cod sursa (job #1585580) | Cod sursa (job #618791) | Cod sursa (job #662341) | Cod sursa (job #849558)
Cod sursa(job #849558)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define TR( C, it ) for( typeof(C.begin()) it = C.begin(); it != C.end(); it++ )
int N, M;
vector <int> muchii[500011];
int visited[100011];
stack <int> stiva;
vector <int> Answer;
void Citire ()
{
ifstream fin ("ciclueuler.in");
fin >> N >> M;
for (int i = 0, a, b; i < M; i++)
{
fin >> a >> b;
muchii[a].push_back (b);
muchii[b].push_back (a);
}
fin.close ();
}
void DFS (int nod)
{
visited[nod] = 1;
for (int i = muchii[nod].size () - 1; i >= 0; i--)
if (!visited[muchii[nod][i]]) DFS (muchii[nod][i]);
}
int Eulerian ()
{
DFS (1);
for (int i = 1; i <= N; i++)
if ((!muchii[i].empty () && !visited[i]) || (muchii[i].size () % 2)) return 0;
return 1;
}
void Sterge (int v, int u)
{
muchii[v].pop_back ();
TR (muchii[u], it)
{
if (*it == v)
{
muchii[u].erase (it);
break;
}
}
}
void Euler (int nod)
{
while (1)
{
if (muchii[nod].empty ()) return;
int w = muchii[nod].back ();
Sterge (nod, w);
stiva.push (nod);
nod = w;
}
}
void Business ()
{
int nod = 1;
do
{
Euler (nod);
nod = stiva.top ();
stiva.pop ();
Answer.push_back (nod);
} while (!stiva.empty ());
}
void Scriere ()
{
ofstream fout ("ciclueuler.out");
if (!Eulerian ())
{
fout << "-1";
fout.close ();
return;
}
while (!Answer.empty ())
{
fout << Answer.back () << " ";
Answer.pop_back ();
}
fout.close ();
}
int main ()
{
Citire ();
Business ();
Scriere ();
return 0;
}