Note de curs, clasele 11-12, 5 octombrie 2012
From Algopedia
Jump to navigationJump to search
Structuri de mulțimi disjuncte
- Ce operații dorim: test de apartenență / uniunea a două mulțimi
- Implementare naivă: vectori (v[x] == v[y] dacă x și y sunt în aceeași mulțime). Analiza complexității
- Implementare arborescentă
- Optimizări: echilibrare și compresia căii
- Analiză de complexitate (fușerită, că mă depășește)
- Exemple: determinarea componentelor conexe, Kruskal, LCA offline
- Discuție tangentă: comparația algoritmilor lui Prim și Kruskal
LCA online și RMQ
- Parcurgeri Euler
- Reducerea LCA online la RMQ
- RMQ: varianta naivă, O(), O(), O(1) per query