Pagini recente » Cod sursa (job #207960) | Cod sursa (job #1328853) | Cod sursa (job #847064) | Cod sursa (job #1914737) | Cod sursa (job #2781738)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#define VMAX 100000
#define NOTFOUND -1
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int V, E, x, y;
vector <int> adj[VMAX];
int deg[VMAX];
stack <int> cpath;
vector <int> epath;
int getIndex(int src, int dest);
void removeEdge(int src, int dest);
void Euler(int src)
{
int u, w;
cpath.push(src);
while (!cpath.empty())
{
u = cpath.top();
if (adj[u].empty())
{
epath.push_back(u);
cpath.pop();
}
else
{
w = adj[u][0];
removeEdge(u, w);
cpath.push(w);
}
}
int n = epath.size();
for (int i = n - 1; i >= 1; --i)
fout << epath[i] + 1 << " ";
}
int main()
{
fin >> V >> E;
while (E--)
{
fin >> x >> y;
x--, y--;
adj[x].push_back(y);
adj[y].push_back(x);
deg[x]++, deg[y]++;
}
bool ok = true;
for (int i = 0; i < V && ok; ++i)
if (deg[i] % 2) ok = false;
if (ok == true) Euler(0);
else fout << -1;
fin.close();
fout.close();
return 0;
}
void removeEdge(int src, int dest)
{
int index = getIndex(src, dest);
if (index != NOTFOUND)
{
E--;
adj[src].erase(adj[src].begin() + index);
adj[dest].erase(adj[dest].begin() + getIndex(dest, src));
}
}
int getIndex(int src, int dest)
{
for (auto it = adj[src].begin(); it != adj[src].end(); ++it)
if (*it == dest) return it - adj[src].begin();
return NOTFOUND;
}