Zadanie 1 [12 punktów]
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.
a)	[2 punkty] Ile maksymalnie krawędzi może mieć graf G?
b)	[6 punkty] 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.
c)	[4 punkty] 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 [8 punktów]

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, …} - Z)

a)	[4 punkty] Zaproponuj strukturę danych, która umożliwi efektywne wykonywanie powyższych operacji. Opisz ich implementacje.
b)	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.

Uwaga: uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowych zaproponowanych algorytmów.