Zadania trudniejsze

Drzewa (jako grafy):

  1. Listonosze, ONTAK 2009
  2. Harbingers, CEOI 2009

Dynamiki:

  1. Leaves, SPOJ

Geometryczne:

  1. Wielokąt wypukły
  2. Tri, CEOI 2009
  3. Zamknąć Godzillę, ONTAK '09

Grafowe:

  1. Autostrady, X OI
  2. Biura, XIV OI
  3. Mafia, BOI 2008
  4. Dla danego grafu nieskierowanego z ważonymi krawędziami znajdź drugie najtańsze drzewo rozpinające. $n \le 10^5, m \le 2*10^5$
  5. Ile trzeba usunąć krawędzi z grafu nieskierowanego, żeby go rozspójnić?
  6. Danych jest n par liczb: $(in_i, out_i)$, $n \le 200$. Czy da się utworzyć n-wierzchołkowy graf skierowany (bez pętli i wielokrotnych krawędzi), dla którego $(in_i, out_i)$ będą oznaczały odpowiednio stopień wejściowy i wyjściowy i-tego wierzchołka? Daj przykład takiego grafu, jeśli się da.

Nieszufladkowalne:

  1. Powódź, XIV OI