• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem w implementacji Find And Union

VPS Starter Arubacloud
0 głosów
176 wizyt
pytanie zadane 29 stycznia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Implementuję find and union z kompresją ścieżek, chcę, żeby przy unionie, wszystkie ścieżki odrazu przepiąć. Gdzieś jest błąd, ale nie wiem gdzie. Ma ktoś pomysł?

#include <iostream>
#include <vector>

using namespace std;

int n = 0, m = 0, wczytana_liczba = 0, a_i = 0, b_i = 0, c_i = 0;
vector<int> rep(2e5+5);

int findd(int v)
{
    if (v == rep[v])
        return v;
    findd(rep[v]);
}

void unionn(int x, int y)
{
    int val_rodzic = findd(y);
    while(true)
    {
        if (x == rep[x])
        {
            rep[x] = val_rodzic;
            break;
        }
        int val = rep[x];
        rep[x] = val_rodzic;
        x = val;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        rep[i] = i;

    while(m--)
    {
        cin >> a_i >> b_i >> c_i;
        if (a_i == 1)
        {
            if (findd(b_i) == findd(c_i))
                printf("TAK\n");
            else
                printf("NIE\n");
        }
        else
        {
            unionn(b_i, c_i);
        }
    }

    return 0;
}

Z góry dziękuję za pomoc!

btw, jest to zadanie: https://sio2.mimuw.edu.pl/c/zwo22/p/wik/ i dostaję signala

2
komentarz 29 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)
btw F&U da się ładniej zaimplementować przepinająć ścieżki wewnątrz funkcji FIND. Wtedy w UNION wystarczy 2 razy wywołać FINDa
komentarz 29 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 29 stycznia 2023 przez pasjonat_algorytmiki

Wsumie nawet nie ładniej, tylko wydajniej, bo czasem nie wywołuję uniona tylko zwykłego finda. Takie coś przechodzi na 100. Takie coś ma już O(N lg N)?

#include <iostream>
#include <vector>

using namespace std;

int n = 0, m = 0, wczytana_liczba = 0, a_i = 0, b_i = 0, c_i = 0;
vector<int> rep(5e5+5);

int findd(int s)
{
    int wyn = 0, v = s;
    while (true)
    {
        if (v == rep[v])
        {
            wyn = v;
            break;
        }
        v = rep[v];
    }
    v = s;
    while (true)
    {
        if (v == rep[v])
            break;
        int syn = rep[v];
        rep[v] = wyn;
        v = rep[v];
    }
    return wyn;
}

void unionn(int x, int y)
{
    rep[findd(x)] = findd(y);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        rep[i] = i;
    while(m--)
    {
        cin >> a_i >> b_i >> c_i;
        if (a_i == 1)
            unionn(b_i,c_i);
        else
        {
            if (findd(b_i) == findd(c_i))
                printf("TAK\n");
            else
                printf("NIE\n");
        }
    }
    return 0;
}

 

2
komentarz 29 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)
Da się finda zapisać jeszcze ładniej (rekurencyjnie) dosłownie w 3 linjjkach :) To powinno działać logarytmicznie, ale jak się UNIONuje po wielkości (czyli łączysz mniejszą grupą do większej) to jedna operacja będzie działała w O(log*n), gdzie log* to iterowany logarytm. Ta funkcja jest chyba <= 5 dla n <= 2^65536, czyli F&U działa wtedy dosłownie w czasie zamortyzowanym stałym

1 odpowiedź

+2 głosów
odpowiedź 29 stycznia 2023 przez tangarr Mędrzec (154,780 p.)
wybrane 29 stycznia 2023 przez pasjonat_algorytmiki
 
Najlepsza
Twój problem polega na tym, że nie czytasz ostrzeżeń zgłaszanych przez kompilator lub używasz zbyt starego, który nie ostrzega cię przed oczywistymi błędami.
Funkcja findd nie zawsze zwraca wynik.
komentarz 29 stycznia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No tak tam powinienem napisać return findd(rep[v]).

Dzięki!

Podobne pytania

0 głosów
1 odpowiedź 91 wizyt
0 głosów
1 odpowiedź 138 wizyt
pytanie zadane 14 grudnia 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
1 odpowiedź 240 wizyt
pytanie zadane 18 listopada 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...