Loại bỏ cạnh
Đề bài
Mô tả
Cho một đồ thị vô hướng, đơn, liên thông và phẳng gồm đỉnh và cạnh. Một đồ thị là phẳng nếu có thể vẽ nó trên mặt phẳng sao cho các cạnh chỉ cắt nhau tại các đầu mút. Ở bài này, đồ thị được cho kèm một cách vẽ như vậy: mỗi đỉnh là một điểm có tọa độ nguyên và mỗi cạnh là đoạn thẳng nối hai đỉnh của nó.
Hãy đếm số cách chọn đúng cạnh khác nhau để xóa khỏi đồ thị sao cho đồ thị còn lại không còn liên thông.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số bộ test (). Tiếp theo là mô tả các bộ test.
- Dòng đầu tiên của mỗi bộ test chứa hai số nguyên và (): số đỉnh và số cạnh của đồ thị.
- dòng tiếp theo, dòng thứ chứa hai số nguyên và (): tọa độ của đỉnh thứ .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và (, ) cho biết có một cạnh nối đỉnh và đỉnh (vẽ bằng đoạn thẳng).
Dữ liệu đảm bảo:
- đồ thị liên thông,
- không có hai điểm nào trùng tọa độ,
- không có hai cạnh nào cắt nhau ngoại trừ tại đầu mút chung (nếu có),
- mỗi cặp điểm được nối bởi tối đa một cạnh,
- tổng trên tất cả các bộ test không vượt quá ,
- tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một số nguyên là số cách chọn đúng cạnh để xóa làm đồ thị mất liên thông.
Ràng buộc
- ; tổng và tổng trên tất cả các bộ test đều không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 8 10 1 1 4 1 4 4 1 4 2 2 3 2 3 3 2 3 1 2 2 3 3 4 4 1 5 6 7 8 1 5 2 6 3 7 4 8 |
64 | Đồ thị gồm hình vuông ngoài , hai cạnh - và - bên trong, và bốn cạnh nối đỉnh với đỉnh . Ví dụ, xóa các cạnh thứ , và (cạnh -, -, -) tách nhóm đỉnh khỏi phần còn lại. |
| 3 3 3 0 0 2 0 0 2 1 2 2 3 3 1 5 4 0 0 1 0 2 0 3 0 0 5 1 2 2 3 3 4 1 5 4 6 0 0 2 0 1 1 1 3 1 2 1 3 2 3 1 4 2 4 3 4 |
1 4 4 |
Bộ test thứ nhất: phải xóa cả ba cạnh của tam giác. Bộ test thứ hai: đồ thị là một cây, xóa bất kỳ trong cạnh đều được. Bộ test thứ ba: đồ thị đầy đủ đỉnh, chỉ có cách là xóa ba cạnh của cùng một đỉnh. |
Bình luận