Bậc phân cách
Đề bài
Mô tả
Trong thế giới ngày càng gắn kết, người ta cho rằng mọi người trên Trái Đất đều có quan hệ với nhau qua không quá sáu bậc phân cách. Trong bài này, bạn cần viết chương trình tìm bậc phân cách lớn nhất của một mạng lưới người.
Với hai người bất kỳ, bậc phân cách giữa họ là số mối quan hệ ít nhất cần đi qua để nối hai người đó với nhau. Với một mạng lưới, bậc phân cách lớn nhất là bậc phân cách lớn nhất giữa hai người bất kỳ trong mạng lưới. Nếu có một cặp người trong mạng lưới không được nối với nhau bởi chuỗi quan hệ nào, mạng lưới được gọi là không liên thông.
Một mạng lưới được mô tả bằng một tập các mối quan hệ đối xứng, mỗi mối quan hệ nối hai người. Hai hình dưới đây vẽ hai mạng lưới, mỗi cạnh là một mối quan hệ giữa hai người. Mạng lưới A có bậc phân cách lớn nhất là . Mạng lưới B không liên thông.
Mạng lưới A:
graph 1 2 3 4 3 2 2 4 name 1 Ashok name 2 Kiyoshi name 3 Ursala name 4 Chun
Mạng lưới B:
graph 1 4 3 2 name 1 Ashok name 2 Kiyoshi name 3 Ursala name 4 Chun
Dữ liệu vào
Dữ liệu gồm nhiều bộ test, mỗi bộ mô tả một mạng lưới người.
Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên (số người trong mạng lưới) và (số mối quan hệ). Tiếp theo là mối quan hệ, mỗi mối quan hệ gồm hai xâu là tên của hai người trong mạng lưới có quan hệ với nhau. Một dòng có thể chứa một hoặc nhiều mối quan hệ, các tên cách nhau bởi một hoặc nhiều dấu cách. Tên của mỗi người là duy nhất và không chứa dấu cách. Vì một người có thể có quan hệ với nhiều người khác, một tên có thể xuất hiện nhiều lần trong một bộ test.
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi mạng lưới, in số thứ tự của mạng lưới (bắt đầu từ ) và bậc phân cách lớn nhất của nó, theo định dạng của ví dụ. Nếu mạng lưới không liên thông, in DISCONNECTED thay cho bậc phân cách. In một dòng trống sau kết quả của mỗi mạng lưới.
Ràng buộc
- , .
- Mỗi tên gồm từ đến chữ cái tiếng Anh (
a-z,A-Z); tên phân biệt chữ hoa và chữ thường (Anvàanlà hai người khác nhau). - Hai tên trong một mối quan hệ luôn khác nhau; một mối quan hệ có thể được liệt kê nhiều lần.
- Trong mỗi bộ test có không quá tên khác nhau. Người không xuất hiện trong mối quan hệ nào vẫn thuộc mạng lưới (và không có quan hệ với ai).
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun 4 2 Ashok Chun Ursala Kiyoshi 6 5 Bubba Cooter Ashok Kiyoshi Ursala Chun Ursala Kiyoshi Kiyoshi Chun 0 0 |
Network 1: 2 Network 2: DISCONNECTED Network 3: DISCONNECTED |
Mạng lưới 1 là mạng lưới A, mạng lưới 2 là mạng lưới B. Mạng lưới 3: Bubba và Cooter chỉ quan hệ với nhau, tách khỏi bốn người còn lại. |
| 5 4 An Binh Binh Chi Chi Dung Dung Em 5 3 An Binh Binh Chi Chi Dung 3 3 an An An AN AN an 2 3 X Y Y X X Y 0 0 |
Network 1: 4 Network 2: DISCONNECTED Network 3: 1 Network 4: 1 |
Ví dụ tự thêm. Mạng lưới 1 là một đường thẳng, An cách Em bậc. Mạng lưới 2 có người nhưng chỉ tên xuất hiện: người thứ năm không quan hệ với ai. Mạng lưới 3 có ba người khác nhau an, An, AN, đôi một quan hệ với nhau. Mạng lưới 4: quan hệ giữa X và Y được liệt kê ba lần. |
Bình luận