Cấu trúc dữ liệu (Graph/Tree)
Disjoint Set Union (DSU)
ID: #47
Xem trên trang chủ
Thời gian (Time)
O(α(n)) gần như O(1)
Không gian (Space)
O(n)
Mô tả nguyên lý
Quản lý các tập hợp rời rạc với hai phép toán chính: Find (tìm gốc) và Union (hợp nhất).
Cài đặt mẫu (Implementation)
function find(&$parent, $i) {
if ($parent[$i] == $i) return $i;
return $parent[$i] = find($parent, $parent[$i]);
}