Problem w implementacji Find And Union

Question

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

Comments

btw F&U da się ładniej zaimplementować przepinająć ścieżki wewnątrz funkcji FIND. Wtedy w UNION wystarczy 2 razy wywołać FINDa

---

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;
}

 

---

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

Answer 1

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.

Comments

No tak tam powinienem napisać return findd(rep[v]).

Dzięki!