Tập hợp rời rạc Disjoint Set Union (DSU) và Phát hiện chu trình

Mục tiêu kiến thức

• Triển khai cấu trúc dữ liệu Disjoint Set Union (Union-Find).
• Áp dụng kỹ thuật Nén đường đi (Path Compression) và Hợp nhất theo kích thước/hạng (Union by Rank/Size).
• Phát hiện chu trình trong đồ thị vô hướng và đếm số thành phần liên thông.

Mô tả bài toán

Viết lớp DisjointSetUnion:

• __init__(self, n: int): Khởi tạo N phần tử có nhãn từ 0 đến n - 1. Ban đầu mỗi phần tử là một tập hợp riêng biệt. Nếu n ≤ 0, raise ValueError("n phai la so nguyen duong").
• find(self, i: int) -> int: Tìm đại diện (gốc) của tập hợp chứa phần tử i, áp dụng kỹ thuật Nén đường đi (parent[i] = find(parent[i])).
• union(self, i: int, j: int) -> bool:
• Hợp nhất hai tập hợp chứa i và j (áp dụng Union by Rank/Size).
• Nếu i và j vốn đã thuộc cùng một tập hợp, trả về False (báo hiệu cạnh (i, j) tạo thành chu trình!).
• Nếu hai phần tử thuộc hai tập hợp khác nhau, tiến hành hợp nhất và trả về True.
• is_connected(self, i: int, j: int) -> bool: Kiểm tra i và j có chung tập hợp hay không.
• connected_components(self) -> int: Trả về số lượng tập hợp rời rạc (thành phần liên thông) hiện tại. Ban đầu là n, giảm đi 1 sau mỗi lần union thành công.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.