Ciklus

Funkcija pocetak_ciklusa iz postavke (preuzeta iz ciklus.cpp sa predavanja) Flojdovim algoritmom nalazi prvi čvor ciklusa. Polazeći od nje napisati funkcije

int duzina_ciklusa(Cvor<int>* pocetak);
void prekini_ciklus(Cvor<int>* pocetak);

Funkcija duzina_ciklusa vraća broj čvorova u ciklusu, odnosno 0 ako ciklusa nema. Posle poziva funkcije prekini_ciklus lista je ponovo obična lista: poslednji čvor pokazuje na nullptr, pa lista može da se obiđe i oslobodi. Ako ciklusa nema, lista se ne menja. Složenost obe funkcije je $O(n)$, a dodatna memorija $O(1)$.

Pitanje za razmišljanje: Zašto lista sa ciklusom krši invarijantu klase Lista? Šta bi se desilo u destruktoru?

Ulaz

U jednom redu učitavaju se brojevi n i p $(1 \le n \le 10^6, -1 \le p &lt; n)$. Program pravi listu od n čvorova sa podacima 0, 1, ..., n - 1. Ako je $p \ge 0$, poslednji čvor pokazuje na čvor sa podatkom p, inače na nullptr.

Izlaz

U prvom redu ispisati podatak prvog čvora ciklusa, odnosno - ako ciklusa nema. U drugom redu ispisati dužinu ciklusa. U trećem redu, posle poziva prekini_ciklus, ispisati broj čvorova liste i podatak poslednjeg čvora.

Primer

Ulaz

8 3

Izlaz

3
5
8 7

Primer

Ulaz

8 -1

Izlaz

-
0
8 7

Postavka

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Vraca pokazivac na prvi cvor ciklusa, odnosno nullptr ako ciklusa nema.
    template <typename T>
    Cvor<T>* pocetak_ciklusa(Cvor<T>* pocetak)
    {
        Cvor<T>* spori = pocetak;
        Cvor<T>* brzi = pocetak;

        while (brzi != nullptr && brzi->sledeci != nullptr) {
            spori = spori->sledeci;
            brzi = brzi->sledeci->sledeci;

            if (spori == brzi) {
                spori = pocetak;
                while (spori != brzi) {
                    spori = spori->sledeci;
                    brzi = brzi->sledeci;
                }
                return spori;
            }
        }
        return nullptr;
    }

    // Vraca broj cvorova u ciklusu, odnosno 0 ako ciklusa nema.
    int duzina_ciklusa(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
        return 0;
    }

    // Prekida ciklus, ako postoji, pa lista ponovo zavrsava sa nullptr.
    void prekini_ciklus(Cvor<int>* pocetak)
    {
        // Ovde ide vasa implementacija
    }

} // namespace matf

// Pravi listu 0, 1, ..., n - 1, ciji poslednji cvor pokazuje na cvor p.
Cvor<int>* napravi(int n, int p)
{
    Cvor<int>* poslednji = new Cvor<int>(n - 1, nullptr);
    Cvor<int>* pocetak = poslednji;
    Cvor<int>* meta = (n - 1 == p) ? poslednji : nullptr;

    for (int i = n - 2; i >= 0; --i) {
        pocetak = new Cvor<int>(i, pocetak);
        if (i == p)
            meta = pocetak;
    }

    poslednji->sledeci = meta;
    return pocetak;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    int n, p;
    std::cin >> n >> p;

    Cvor<int>* lista = napravi(n, p);

    Cvor<int>* c = matf::pocetak_ciklusa(lista);
    if (c == nullptr)
        std::cout << "-" << std::endl;
    else
        std::cout << c->podatak << std::endl;

    std::cout << matf::duzina_ciklusa(lista) << std::endl;

    matf::prekini_ciklus(lista);

    int broj = 0;
    Cvor<int>* poslednji = nullptr;
    for (Cvor<int>* q = lista; q != nullptr; q = q->sledeci) {
        ++broj;
        poslednji = q;
    }
    std::cout << broj << " " << poslednji->podatak << std::endl;

    oslobodi(lista);
    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "lista.h"   // zbog strukture Cvor

namespace matf {

    // Vraca pokazivac na prvi cvor ciklusa, odnosno nullptr ako ciklusa nema.
    template <typename T>
    Cvor<T>* pocetak_ciklusa(Cvor<T>* pocetak)
    {
        Cvor<T>* spori = pocetak;
        Cvor<T>* brzi = pocetak;

        while (brzi != nullptr && brzi->sledeci != nullptr) {
            spori = spori->sledeci;
            brzi = brzi->sledeci->sledeci;

            if (spori == brzi) {
                spori = pocetak;
                while (spori != brzi) {
                    spori = spori->sledeci;
                    brzi = brzi->sledeci;
                }
                return spori;
            }
        }
        return nullptr;
    }

    // Vraca broj cvorova u ciklusu, odnosno 0 ako ciklusa nema.
    int duzina_ciklusa(Cvor<int>* pocetak)
    {
        Cvor<int>* c = pocetak_ciklusa(pocetak);
        if (c == nullptr)
            return 0;

        int duzina = 1;
        for (Cvor<int>* p = c->sledeci; p != c; p = p->sledeci)
            ++duzina;
        return duzina;
    }

    // Prekida ciklus, ako postoji, pa lista ponovo zavrsava sa nullptr.
    void prekini_ciklus(Cvor<int>* pocetak)
    {
        Cvor<int>* c = pocetak_ciklusa(pocetak);
        if (c == nullptr)
            return;

        // Poslednji cvor je onaj koji pokazuje nazad, na prvi cvor ciklusa.
        Cvor<int>* poslednji = c;
        while (poslednji->sledeci != c)
            poslednji = poslednji->sledeci;
        poslednji->sledeci = nullptr;
    }

} // namespace matf

// Pravi listu 0, 1, ..., n - 1, ciji poslednji cvor pokazuje na cvor p.
Cvor<int>* napravi(int n, int p)
{
    Cvor<int>* poslednji = new Cvor<int>(n - 1, nullptr);
    Cvor<int>* pocetak = poslednji;
    Cvor<int>* meta = (n - 1 == p) ? poslednji : nullptr;

    for (int i = n - 2; i >= 0; --i) {
        pocetak = new Cvor<int>(i, pocetak);
        if (i == p)
            meta = pocetak;
    }

    poslednji->sledeci = meta;
    return pocetak;
}

void oslobodi(Cvor<int>* pocetak)
{
    while (pocetak != nullptr) {
        Cvor<int>* stari = pocetak;
        pocetak = pocetak->sledeci;
        delete stari;
    }
}

int main()
{
    int n, p;
    std::cin >> n >> p;

    Cvor<int>* lista = napravi(n, p);

    Cvor<int>* c = matf::pocetak_ciklusa(lista);
    if (c == nullptr)
        std::cout << "-" << std::endl;
    else
        std::cout << c->podatak << std::endl;

    std::cout << matf::duzina_ciklusa(lista) << std::endl;

    matf::prekini_ciklus(lista);

    int broj = 0;
    Cvor<int>* poslednji = nullptr;
    for (Cvor<int>* q = lista; q != nullptr; q = q->sledeci) {
        ++broj;
        poslednji = q;
    }
    std::cout << broj << " " << poslednji->podatak << std::endl;

    oslobodi(lista);
    return 0;
}