Traseu de învățare — Clasele XI–XII

Clasele XI–XII sunt vârful traseului: grafuri, arbori și structuri de date avansate. Pleci de la noțiunile de bază despre grafuri, înveți să le reprezinți și să le parcurgi (BFS, DFS, componente conexe și tare conexe), apoi treci la drumuri minime (Dijkstra, Bellman-Ford, Roy-Floyd), arbori de cost minim (Kruskal, Prim), structuri arborescente (heap, BST, DSU) și programare dinamică avansată (pe arbori, pe grafuri, cu bitmask). La extensia națională adaugi grafuri avansate, LCA, Fenwick/Segment Tree, RMQ și tehnicile de performanță. Până la final ai întreaga trusă a unui olimpic de liceu.

Harta nivelurilor

Clasele XI–XII acoperă Nivel 6 — Grafuri și arbori și tot Nivel 7 — Performanță.

1. Nivel 6 — Grafuri și arbori: BFS, DFS, componente, drumuri minime, MST, DSU.
2. Nivel 7 — Performanță: DP avansat, LCA, Fenwick/Segment Tree, RMQ, Sqrt Decomposition, Mo, Meet in the Middle, Mobius, matrici logaritmice.

Presupune ca date deja stăpânite toți Nivelii 1–5 (clasele IX–X), inclusiv recursivitate, backtracking și DP de bază.

Traseul pe capitole

1. Grafuri — noțiuni de bază

• Ce înveți / de ce contează: graf orientat/neorientat, lanț, drum, ciclu, grad, conexitate, tare conexitate, ponderat, arbore și arbore parțial de cost minim. Vocabularul fără de care nimic nu are sens.
• Deblochează: tot restul liceului; lecția-punte „transformarea unei probleme într-un graf" e abilitatea de modelare centrală.

2. Tipuri speciale de grafuri

• Ce înveți / de ce contează: complet, hamiltonian, eulerian, bipartit, turneu. Recunoști structuri cu proprietăți speciale.
• Deblochează: algoritmii dedicați (eulerian, bipartit) din capitolele următoare.

3. Reprezentarea grafurilor

• Ce înveți / de ce contează: matrice de adiacență, liste de adiacență, lista muchiilor/arcelor, variantele cu costuri. Alegi structura potrivită pentru dimensiunea problemei.
• Deblochează: implementarea eficientă a oricărui algoritm pe grafuri.

4. Parcurgeri și conectivitate

• Ce înveți / de ce contează: BFS, DFS, componente conexe, componente tare conexe (Kosaraju), graful CTC, parcurgere euleriană. Cele două parcurgeri fundamentale și aplicațiile lor.
• Deblochează: aproape tot — sortare topologică, drumuri, DP pe grafuri. Lecția-punte „DFS ca unealtă generală" e esențială.

5. Drumuri și ordine în grafuri

• Ce înveți / de ce contează: Roy-Warshall, sortare topologică, descompunere DAG pe niveluri, Dijkstra, Bellman-Ford, Roy-Floyd, lanț/ciclu hamiltonian și eulerian.
• Deblochează: problemele de cost minim și de ordonare; lecția-punte „parcurgere vs drum minim" lămurește o confuzie frecventă.

6. Structuri de date arborescente

• Ce înveți / de ce contează: arbori cu rădăcină și binari, reprezentare secvențială, heap, BST, interogări/actualizări, Union-Find / DSU. Structurile care răspund rapid la întrebări.
• Deblochează: Kruskal (prin DSU), heap-ul din Dijkstra/Prim, structurile avansate de la extensie.

7. Arbori și arbori de cost minim

• Ce înveți / de ce contează: proprietățile arborilor, arbori parțiali, Kruskal, Prim. Construiești rețeaua de cost minim care conectează totul.
• Deblochează: problemele clasice de MST; lecția-punte „de ce un arbore cu n noduri are n−1 muchii" cimentează intuiția.

8. Programare dinamică avansată

• Ce înveți / de ce contează: recapitulare DP, DP pe arbori, DP pe grafuri, DP pe stări exponențiale, DP cu bitmask. DP-ul modelat pe structuri complexe.
• Deblochează: cele mai grele probleme de la națională; lecția-punte „modelarea unei probleme ca DP" e arta supremă.

9. Grafuri avansate — Etapă națională (opțional, dar recomandat)

• Ce înveți / de ce contează: puncte de articulație, punți, componente biconexe, algoritmul lui Dial. Analiza fină a structurii unui graf.
• Deblochează: probleme de robustețe a rețelelor și de conectivitate avansată.

10. Arbori și structuri avansate — Etapă națională (opțional, dar recomandat)

• Ce înveți / de ce contează: LCA, diametrul arborelui, Fenwick Tree, Segment Tree, RMQ. Structuri pentru interogări și actualizări rapide.
• Deblochează: problemele cu interogări pe interval — coloana vertebrală a concursurilor de top.

11. Tehnici avansate — Etapă națională (opțional, dar recomandat)

• Ce înveți / de ce contează: Square Root Decomposition, algoritmul lui Mo, Meet in the Middle, ridicarea matricilor la putere, recurențe liniare cu matrici, includere-excludere, funcția Mobius.
• Deblochează: ultimul nivel de performanță; lecția-punte „cum alegi între Fenwick, Segment Tree, RMQ, Sqrt și Mo" e ghidul de decizie al olimpicului matur.

Borne / checkpoints

• După Parcurgeri: rezolvi componente conexe, sortare topologică și componente tare conexe pe grafuri mari.
• După Drumuri minime + MST: alegi corect între Dijkstra, Bellman-Ford și Roy-Floyd, și construiești un arbore parțial de cost minim cu Kruskal/Prim.
• După DP avansat: rezolvi un DP pe arbore și un DP cu bitmask (ex. comis-voiajor pe stări mici).
• După structuri avansate: răspunzi la interogări pe interval cu Segment Tree / Fenwick și afli LCA în timp logaritmic — exact nivelul ONI clasele XI–XII.

Traseul olimpicului

Capitolele 1–8 sunt nucleul de liceu și acoperă etapa județeană și o bună parte din națională. Capitolele 9–11 (extensii naționale) sunt diferența dintre un rezultat bun și un loc pe podium. Strategia: nu te repezi la Segment Tree înainte de a stăpâni BFS/DFS și DP-ul — structurile avansate presupun parcurgeri solide. După ce ai trusa completă, pasul „dincolo de minim" e antrenamentul pe probleme reale (arhiva OJI/ONI) și combinarea tehnicilor: un DP pe arbore cu LCA, un Dijkstra pe stări, o numărare cu includere-excludere și Mobius.

Capcane de parcurs

• Sari la Segment Tree / DP avansat fără parcurgeri solide. Grafurile sunt fundația; fără BFS/DFS naturale, restul se prăbușește. Roadmap-ul pune parcurgerile înaintea drumurilor și structurilor.
• Memorezi algoritmii în loc să modelezi. Mulți știu Dijkstra dar nu văd când o problemă este un graf. Lecțiile-punte de modelare (graf, DP) sunt exact antidotul.
• Colecționezi structuri fără criteriu de alegere. Fenwick, Segment Tree, RMQ, Sqrt, Mo rezolvă lucruri suprapuse. Lecția-punte de la capitolul 11 te învață când alegi fiecare — altfel pierzi timp prețios la concurs alegând greșit.