Jak przyspieszyć zadanie na Union Finda

Question

Mam takie zadanko

Jaś ma N kamieni ponumerowanych od 1 do N. Na początku każdy kamień znajduje się w osobnym worku.
Jaś chciałby wykonac Q operacji postaci:
0 a b -- jeżeli kamień o numerze a i kamień o numerze b są w tym samym worku to wypisz Tak, inaczej wypisz Nie.
1 a b -- wrzuć wszystkie kamienie, które znajdują sie w tym samym worku co a lub b do jednego worka.

Wejście

W pierwszym wierwszu znajdują się dwie liczby naturalne N i Q (1 <= N, Q <= 1000000).
W następnych Q wierszach znajduje się po trzy liczby naturalne t, a, b (0 <= t <= 1, 1 <= a, b <= N), gdzie t to typ zapytania, b i a to numery kamieni.

Wyjście

Na każde zapytanie typu 0 wypisz Tak lub Nie.

Przykład

Dla danych wejściowych

5 7
1 2 3
0 2 3
0 1 2
1 4 5
0 3 4
1 3 5
0 2 5

poprawną odpowiedzią jest

Tak
Nie
Nie
Tak

Napisałem kod, który działa. Tylko jest za wolny.

#include <iostream>
int tablica2[1000100]= {};int xd,lol;
    int tablica3[1000100];
bool tab[1000100];

using namespace std;
int Find(int a){// szukam "rodzica" liczby. Jako że skracam ścieżki to jest to albo ona sama lub jej tablica3
if(tablica3[a]==a){
    return a;
}
else{

 tablica3[a]=Find(tablica3[a]);}
return tablica3[a];


}
void Union(int a, int b)
{
	xd=Find(a);//tu wczytuje rodziców liczb żeby potem nie powtarzać operacji
	lol=Find(b);
    if(tablica2[xd]<=tablica2[lol])
	{
		tablica2[xd]+=tablica2[lol];
		tablica3[xd]=lol;
	}
	else
	{
		tablica2[xd]+=tablica2[lol];
		tablica3[lol]=xd;
	}

}



int main()
{  ios_base::sync_with_stdio(false);



    int ilek,ilep,pyta,d,e,c=0;
    cin>>ilek>>ilep;
    for(int i=0; i<ilek; i++)
    {
        tablica3[i+1]=i+1;tablica2[i+1]++;

    }
    for(int i=0; i<ilep; i++)
    {
        cin>>pyta>>d>>e;
if(pyta==1){Union(d,e);}



        else
        {
            if( Find(d)==Find(e))
            {
                tab[c]=true;
                c++;
            }
            else
            {
                tab[c]=false;
                c++;
            }
        }
    }

    for(int i=0; i<c; i++)
    {
        if(tab[i]==true)
        {
            cout<<"Tak"<<endl;
        }
        else
        {
            cout<<"Nie"<<endl;
        }
    }

















}

Mogę prosić o pomoc?

 

Comments

https://www.google.com/amp/s/www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/amp/

Spojrz na ta imolementacje. Nie rozumiem po co rezerwujesz tablice o wielkosci 1 mln komorek, co lacznie daje ich 3 mln, skoro uyzjesz np. 5.

Uzyj lepiej wektorow i przekazuj tablice do funkcji

---

@Toady2004, w linii 24. masz błąd. Powinno być chyba:

tablica2[lol]+=tablica2[xd];