Note de curs, clasele 11-12, 26 octombrie 2012

Teme mai vechi

• să se găsească cele mai mici k elemente dintr-un vector în ordine sortată / nesortată
  • analize de complexitate pentru sortare, select, min-heap, max-heap

Sortare topologică

• cealaltă metodă, cu contorizarea gradelor la intrare
  • demonstrație că merge tot în O(V + E)

Componente tare conexe

• metoda cu două parcurgeri în adâncime (a doua în ordinea dictată de timpii f[u] rezultați din prima)
• proprietăți ale grafului componentelor tare conexe, G^SCC
  • demonstrație că este un dag

Componente biconexe & co

• componente biconexe
• puncte de articulație
• punți

Probleme

• numărarea drumurilor de la u la v într-un dag
• ce se poate întâmpla cu componentele tare conexe dacă scot/adaug o muchie?
• codul Prüfer O(n)