D. DISJOINTSET – Các tập rời nhau

Disjoint-set hiểu một cách đơn giản là một cách lưu trữ các tập hợp phần tử của một tập lớn cho trước với phép toán thường được quan tâm tới trong disjoint-set là:

• : tạo ra một tập chỉ có ;
• : tìm tập hợp chứa nút ;
• : ghép hai tập hợp chứa và với nhau.

Xét bài toán: Cho một đồ thị gồm đỉnh được đánh số từ đến , giữa hai đỉnh bất kỳ đều có thể nối hoặc không nối với nhau. Ở trạng thái ban đầu tất cả các đỉnh đều không có cạnh nối. Bạn được cho một số yêu cầu, trong đó mỗi yêu cầu có một trong hai dạng:

• : có ý nghĩa là bạn cần nối hai đỉnh và bằng một cạnh.
• : có ý nghĩa là bạn cần cho biết với trạng thái như hiện tại thì hai đỉnh và có thuộc cùng một thành phần liên thông hay không?

Dữ liệu vào:

• Dòng đầu tiên ghi một số nguyên dương là số yêu cầu;
• Trong dòng tiếp theo, mỗi dòng ghi ba số nguyên dương với ý nghĩa có yêu cầu loại với hai đỉnh và .

Dữ liệu ra:

• Với mỗi yêu cầu dạng (với ) bạn cần ghi ra số hoặc trên một dòng tùy thuộc hai đỉnh và không thuộc hoặc thuộc cùng một thành phần liên thông.

Ví dụ:

Dữ liệu vào:

9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2

Dữ liệu ra:

0
0
1
0
1
0

Giới hạn:

• .