2. Klasówka 2009/10#
Zadanie 1#
Kaktusem nazywamy graf spójny, w którym każda dwuspójna składowa jest krawędzią lub cyklem. Niech \(G\) będzie \(n\)-wierzchołkowym kaktusem, zadanym przez listy sąsiedztwa.
Ile maksymalnie krawędzi może mieć graf \(G\)?
Wzbogać algorytm przeszukiwania w głąb grafu \(G\) w taki sposób, żeby obliczał także liczbę cykli nieparzystej długości w tym grafie.
Załóżmy, że krawędziom grafu \(G\) przypisano wagi całkowitoliczbowe. Zaproponuj algorytm, który w czasie liniowym znajdzie minimalne drzewo rozpinające grafu \(G\).
Zadanie 2#
Niech \(Z\) będzie dynamicznym skończonym podzbiorem zbioru dodatnich liczb całkowitych, początkowo pustym. Rozważmy następujące trzy operacje na zbiorze \(Z\):
\(Insert(Z, k)\):: \(Z := Z + \{k\}\)
\(Delete(Z, k)\):: \(Z := Z - \{k\}\)
\(FirstNotIn(Z)\):: return \(min(\{1, 2, 3, \cdots\} - Z)\)
Zaproponuj strukturę danych, która umożliwi efektywne wykonywanie powyższych operacji. Opisz ich implementacje.
Dana jest dodatnia liczba całkowita \(n\), a następnie ciąg złożony z \(n\) operacji \(Insert\) lub \(FirstNotIn\). Zaproponuj efektywny algorytm, który obliczy ciąg wyników kolejnych operacji \(FirstNotIn\).