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

Bir qraf $N$ zirvədən ibarətdir. Əvvəlcə bu qraf boşdur. Sizə $M$ sorğunu emal etmək tapşırılıb:

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

• İki zirvə $a$ və $b$ üçün onların eyni ağacda olub-olmadığını müəyyən edin.

Problemin həlli

Yolların sıxılması ilə DSU (Disjoint Set Union) alqoritmini tətbiq edək:

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

Siz bu həllin uzun müddət işləyəcəyi bir test hazırlamalısınız. Daha dəqiq desək, calc_leader funksiyasının çağırışlarının sayı $1/4M{\log }_{2}M$-dən az olmayacaq bir test hazırlamalısınız.

Giriş verilənləri

Giriş faylı iki tam ədəd $N$ və $M$ ($1\le N\le 10^6$, $1\le M\le 10^5$, $M\le N$) ehtiva edir.

Çıxış verilənləri

$M$ sətir çıxarın. $i$-ci sətir $1xy$ şəklində olmalıdır, əgər $i$-ci sorğu $x$ zirvəsindən $y$ zirvəsinə kənar əlavə etməkdən ibarətdirsə, və ya $0xy$ şəklində olmalıdır, əgər soruşulursa, $x$ və $y$ zirvələri eyni ağacda yerləşir.

Nümunələr