Daha bir ağac məsələsi

$N$ zirvədən ibarət olan, əvvəlcə boş olan bir qrafı nəzərdən keçirək. Sizə aşağıdakı iki tip $M$ sorğunu emal etmək tapşırılır:

• v_1 zirvəsindən v_2 zirvəsinə kənar əlavə edin, burada v_1 və v_2 müxtəlif ağaclarda yerləşir və v_2 öz ağacının köküdür.

• İki $a$ və $b$ zirvəsinin eyni ağacda olub-olmadığını yoxlayın.

Həll

Bu əməliyyatların səmərəli yerinə yetirilməsi üçün yol sıxılması ilə Birleşmə-Ayırma (Union-Find) verilənlər strukturundan istifadə edəcəyik:

int n, m, l[NMAX];
int calc_leader(int v)
{
    if (l[v] != v)
        l[v] = calc_leader(l[v]);
    return l[v];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        l[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &z, &x, &y);
        if (z == 1)
            l[y] = x;
        else
            if (calc_leader(x) == calc_leader(y))
                printf("YES\n");
            else
                printf("NO\n");
    }
}

Sizdən tələb olunan - bu həlldə funksiyanın uzun müddət işləyəcəyi bir test hazırlamaqdır. Daha dəqiq desək, calc_leader funksiyasına çağırışların sayı ən azı \frac{1}{4} M \log_2 M olmalıdır.