union_find_array

Khoi tao Disjoint-Set Union (DSU) tren 7 phan tu A..G. Moi phan tu la goc cua chinh no: $parent[x] = x$, $rank[x] = 0$. Chua co mui ten nao – moi node deu doc lap. Ta se dung annotation arrows giua cac o cua mang $parent[]$ de the hien quan he cha-con.

$union(A, B)$: goc cua A la A, goc cua B la B. Rank bang nhau nen gan B lam con cua A: $parent[1] = A$. Ve mui ten tu cell[1] den cell[0] (B tro ve A). Thanh phan: $\{A, B\}$ voi goc A.

$union(C, D)$: goc C va goc D khac nhau. Gan D lam con cua C: $parent[3] = C$. Mui ten cell[3] $\to$ cell[2]. Thanh phan: $\{A,B\}, \{C,D\}, \{E\}, \{F\}, \{G\}$.

$union(E, F)$: gan F lam con cua E: $parent[5] = E$. Mui ten cell[5] $\to$ cell[4]. Thanh phan: $\{A,B\}, \{C,D\}, \{E,F\}, \{G\}$.

$union(A, C)$: $find(A) = A$, $find(C) = C$. Goc khac nhau. Rank bang nhau nen gan C lam con cua A: $parent[2] = A$, $rank[0] = 1$. Mui ten cell[2] $\to$ cell[0]. Bay gio D la con cua C, C la con cua A. Tim goc cua D can di $D \to C \to A$ (2 buoc). Day la chuoi se duoc nen boi path compression.

$find(D)$ voi path compression – Buoc 1: bat dau tai D (cell[3]). $parent[3] = C$. Di theo mui ten cell[3] $\to$ cell[2] (D tro ve C). D chua phai goc, can tiep tuc.

$find(D)$ – Buoc 2: tu C (cell[2]). $parent[2] = A$. Di theo mui ten cell[2] $\to$ cell[0] (C tro ve A). Tiep tuc tim goc.

$find(D)$ – Buoc 3: den A (cell[0]). $parent[0] = A$, day la goc! $find(D)$ tra ve A. Bay gio thuc hien path compression: doi parent cua D tu C thanh A, xoa mui ten cu va ve mui ten moi truc tiep den goc.

Path compression hoan tat: $parent[3] = A$. Mui ten cu cell[3] $\to$ cell[2] (D $\to$ C) da duoc thay the boi mui ten moi cell[3] $\to$ cell[0] (D $\to$ A, mau path). Lan goi $find(D)$ tiep theo se la $O(1)$ vi D tro truc tiep den goc A.

$union(A, E)$: $find(A) = A$, $find(E) = E$. Goc khac nhau. $rank[0] = 1 > rank[4] = 0$, nen gan E lam con cua A: $parent[4] = A$. Mui ten cell[4] $\to$ cell[0]. Bay gio A la goc cua tat ca tru G. F van tro ve E ($parent[5] = E$), chua duoc nen.

Trang thai cuoi: $parent[] = [A, A, A, A, A, E, G]$. Hau het cac mui ten tro truc tiep den cell[0] (goc A) nho union by rank va path compression. Cell[5] (F) van tro ve cell[4] (E) vi $find(F)$ chua duoc goi – DSU chi nen duong di khi $find$ duoc thuc thi. Cell[6] (G) van la goc doc lap. Do phuc tap khau hao: $O(\alpha(n))$ moi thao tac.