Pagini recente » Cod sursa (job #1085749) | Cod sursa (job #9099) | Cod sursa (job #364780) | Cod sursa (job #2275711) | Cod sursa (job #2399497)
#include <fstream>
#include <vector>
#include <unordered_set>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
using US = unordered_multiset<int>;
using VUS = vector<US>;
using VI = vector<int>;
int n;
VUS G;
VI ciclu;
void citesteGraf();
void detCiclu(int x);
bool esteEulerian();
int main() {
citesteGraf();
if ( !esteEulerian() ) {
fout << -1;
} else {
detCiclu(1);
for (size_t i = 0; i < ciclu.size() - 1; ++i)
fout << ciclu[i] << ' ';
}
}
int x, y, m;
void detCiclu(int x) {
while (!G[x].empty()) {
auto it = G[x].begin(); y = *it;
G[x].erase(it); // sterg un y in G[x] (asta mai intai, ca sa nu invalidez iteratorul begin()
it = G[y].find(x);
if (it != G[y].end())
G[y].erase(it); // sterg un x in G[y]
detCiclu(y);
}
ciclu.emplace_back(x);
}
bool esteEulerian() {
for (auto ms : G)
if (ms.size() & 1)
return false;
return true;
}
void citesteGraf() {
fin >> n >> m;
G = VUS(n + 1);
while (m--) {
fin >> x >> y;
G[x].emplace(y);
G[y].emplace(x);
}
}