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

From Algopedia
Jump to: navigation, search

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, GSCC
    • 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)