Thành phần liên thông & Union-Find Tier 5 · L36
Ba mô-đun tương tác: (1) Union-Find với path compression, (2) đếm component khi thêm cạnh động, (3) phát hiện chu trình.
1. Union-Find animator find + path compression
6 phần tử 0..5. Union by size treo cây nhỏ dưới cây lớn.
Find nén đường — mọi đỉnh trên đường trỏ thẳng tới root, cây phẳng hơn.
root
phần tử
vừa thao tác
Bấm các nút union/find để xem rừng cây biến đổi.
2. Đếm component động online — thêm cạnh
7 đỉnh. Thêm từng cạnh; mỗi union thành công giảm số component đi 1. Cạnh nối hai đỉnh đã cùng tập không đổi count.
Cạnh:
—
Số component: 7
Đỉnh tô cùng màu = cùng component.
3. Phát hiện chu trình undirected cycle
Thêm cạnh lần lượt. Nếu hai đỉnh đã cùng tập trước đó → cạnh đóng vòng → chu trình (tô đỏ).
Cạnh:
—
Chưa có cạnh nào.
| Cạnh | Union OK? | Kết luận |
|---|