Meno: Michal Korbela
Škola: Gybmnázium J.J. Bánovce nad B. Radlinského 665/2, 95701
Adresa domov: Brezolupy 160, 95701
Trieda: kvinta
Úloha č.4 - Popis



Na začiatku je nutné, zapamätať si kamarátstva.
tie si zapíšeme do poľa "pole".

Potom začneme testovať:
Ak nemá nejaký žiak aspoň dvoch kamarátov je nám nanič. Ak by mal byť v 3 člennom družstve musí sa kamarátiť s tými 2.
Ak nájdeme takého žiaka, ktorý s kamaráti  s aspoň dvomi žiakmi tak ich pokladajme za 2. a 3. člena týmu.
Potom už len otestujeme či sa 2. kamaráti s tretím ak áno, tak máme tým.
Takto postupujeme až kým neprídeme ku n-2 žiakovi. n-1 žiaka už testovať nemusíme, pretože ten sa nanajvíš môže kamarátiť len s n-tým žiakom.
Iné týmy dostať nemôžme, pretože ak by mal byť niekto v nejakov týme a nájdeme tým v ktorom sa nachádzajú v tom týme v ktorom by mal byť, tak mu už zostáva len 1 kamarátstvo - a tým pádom ho nemôžme nikde zaradiť. Existuje vždy len určitý počet týmov ktorý sa dá získať z daných kamarátstiev.


Časová zložitosť: závisí to od počtu žiakov tj. je lineárna O(N)
Pamäťová zložitosť tiež závisí od počtu žiakov O(N)