Đẳng cấu cây I
Đề bài
Mô tả
Cho hai cây có gốc, mỗi cây gồm đỉnh đánh số từ đến , và gốc của cả hai cây đều là đỉnh .
Hai cây có gốc được gọi là đẳng cấu nếu có thể vẽ lại một cây (đổi tên các đỉnh và đổi thứ tự các con của mỗi đỉnh) để nó trông giống hệt cây còn lại, trong đó gốc phải tương ứng với gốc. 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à là cha của trong cây thứ nhất khi và chỉ khi là cha của 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 |
NO YES |
Bộ 1: cây thứ nhất là đường đi (gốc có một con), cây thứ hai có gốc với hai con. Bộ 2: cả hai cây đều là đường đi xuất phát từ gốc . |
| 1 4 1 2 1 3 3 4 4 1 1 3 2 4 |
YES | Ở cả hai cây, gốc có hai con: một con là lá, con còn lại có đúng một con là lá (: , , ). |
Bình luận