trang chủ / đề bài / icpcwf06_i

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à 2. 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 P (số người trong mạng lưới) và R (số mối quan hệ). Tiếp theo là R 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ố 0.

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ừ 1) 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

  • 2≤P≤50, 1≤R≤2000.
  • Mỗi tên gồm từ 1 đến 20 chữ cái tiếng Anh (a-z, A-Z); tên phân biệt chữ hoa và chữ thường (An và an là 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á P 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á 100 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 4 bậc. Mạng lưới 2 có 5 người nhưng chỉ 4 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0