Cấu trúc dữ liệu (Graph/Tree)

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 1)

Cấu trúc dữ liệu (Graph/Tree)

Disjoint Set Union (DSU)

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