Đẳng cấu cây II
Đề bài
Mô tả
Cho hai cây (không có gốc), mỗi cây gồm đỉnh đánh số từ đến .
Hai cây được gọi là đẳng cấu nếu có thể vẽ lại một cây (đổi tên các đỉnh) để nó trông giống hệt cây còn lại. Nói cách khác, tồn tại một song ánh từ tập đỉnh cây thứ nhất sang tập đỉnh cây thứ hai sao cho và được nối bởi một cạnh trong cây thứ nhất khi và chỉ khi và được nối bởi một cạnh trong cây thứ hai.
Với mỗi bộ dữ liệu, hãy cho biết hai cây có đẳng cấu hay không.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên , số bộ dữ liệu.
- Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa số nguyên .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một cạnh của cây thứ nhất.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một cạnh của cây thứ hai.
Dữ liệu ra
Với mỗi bộ dữ liệu, in YES nếu hai cây đẳng cấu, ngược lại in NO.
Ràng buộc
- Tổng các giá trị không vượt quá
- , ; mỗi bộ cạnh tạo thành một cây
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 1 2 2 3 1 2 1 3 3 1 2 2 3 1 3 3 2 |
YES YES |
Mọi cây đỉnh đều là một đường đi. Bộ 1: , , . |
| 1 4 1 2 2 3 3 4 1 2 1 3 1 4 |
NO | Cây thứ nhất là đường đi, cây thứ hai có một đỉnh bậc . |
Bình luận