Per risolvere questo problema (eulerian path, in soldoni) ho pensato di applicare l’algoritmo di Hierholzer[0], che in teoria è O(m). m in questo caso è al massimo 10^6 quindi dovrebbe andare tutto bene, ma va in TLE negli ultmi task e quindi prendo 75.
Come l’ho implementato, in pseudocodice:
eulerian_path(list sol, node u)
sol = lista di nodi nell'eulerian path
u = nodo corrente
per ogni figlio v di u
se in sol non c'è l'arco (u, v) né l'arco (v, u)
inserisci v in sol dopo u
eulerian_path(sol, v)
Utilizzando un array di std::unordered_map<int, bool>
per vedere se gli archi sono nella lista, l’accesso è O(1), quindi non dovrebbe essere quello il problema[1]. Una std::list
ha inserimento in O(1), quindi di nuovo non credo sia questo il problema. Con O(2m) controlli (visto che controlla ogni arco e il suo contrario) e O(m) inserimenti (entrambe le parti di ogni arco), la complessità dovrebbe essere appunto O(m). Per stampare mi limito a scorrere la lista al contrario utilizzando un iterator, quindi di nuovo O(m). Cosa non ho considerato? Ne sto uscendo pazzo!
Il codice:
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int MAX = 100000;
unordered_map<int, bool> vis[MAX];
vector<int> g[MAX];
list<int> sol;
int euler_path(list<int>::iterator it, int u) {
for (auto v : g[u]) {
if (!vis[v][u] && !vis[u][v]) {
vis[v][u] = 1;
vis[u][v] = 1;
euler_path(sol.emplace(it, u), v);
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
size_t n, m;
int a, b;
int start, end_;
scanf("%d %d %d %d", &n, &m, &start, &end_);
--start;
--end_;
for (size_t i = 0; i < m; i++) scanf("%d %d", &a, &b), g[--a].pb(--b), g[b].pb(a);
euler_path(begin(sol), start);
for (auto i = prev(end(sol)); i != begin(sol); i = prev(i)) printf("%d %d\n", *i + 1, *prev(i) + 1);
printf("%d %d\n", *begin(sol) + 1, end_ + 1);
return 0;
}
[0] https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm
[1] Nel caso peggiore è O(n), d’accordo, ma ho provato anche con una std::map
con accesso sempre in O(\log n) e comunque dà 75. Un array di std::vector<bool>
dà segnale 11, probabilmente perché troppo grande per i limiti di memoria. Una matrice statica è troppo grande per stare nello stack e fallisce la compilazione, una matrice dinamica con new
fa 55 punti e un tot di segnali 11. Domanda bonus: quando ci sono matrici molto “sparse” (es. matrici di adiacenze di grafi, memo per DP con parametri potenzialmente molto grandi e diversi tra loro), conviene usare una std::unordered_map
o altro?