trang chủ / đề bài / thhv19_chg_11_c

Mạng máy tính

Đề bài

Mô tả

Có N máy tính đánh số từ 1 đến N và M dây cáp mạng. Giữa 2 máy tính có thể có một hoặc nhiều đường dây cáp mạng nối chúng, không có cáp mạng nối một máy với chính nó. Hai máy tính có thể truyền dữ liệu cho nhau nếu có đường cáp nối trực tiếp giữa chúng hoặc truyền qua một số máy trung gian.

Một tập S các máy tính được gọi là hệ thống an toàn nếu các máy tính thuộc S truyền được dữ liệu cho nhau, và dù một máy tính bất kỳ bị tấn công thì trong số những máy tính còn lại, những máy tính thuộc tập S vẫn có thể truyền được dữ liệu cho nhau. Máy tính bị tấn công có thể thuộc hoặc không thuộc S; nó không thể gửi, nhận hay chuyển tiếp dữ liệu nữa. Dữ liệu được phép đi qua các máy trung gian không thuộc S.

Yêu cầu: Xác định số lượng lớn nhất có thể các máy tính của tập S.

Dữ liệu vào

  • Dòng đầu tiên chứa 2 số nguyên N, M (1≤N≤3000, 0≤M≤10000).
  • M dòng tiếp theo ghi thông tin về các dây cáp mạng, mỗi dòng gồm 2 chỉ số khác nhau của 2 máy được dây đó nối trực tiếp.

Dữ liệu ra

Ghi ra một số nguyên duy nhất là số lượng máy tính lớn nhất tìm được.

Ràng buộc

  • 1≤N≤3000.
  • 0≤M≤10000.
  • Mỗi dây cáp nối hai máy tính khác nhau; hai máy tính có thể được nối bởi nhiều dây cáp.

Ví dụ

Input Output Giải thích
8 10
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 8
8 1		 4 Tập S={1,6,7,8} nằm trên vòng 1−6−7−8−1: mất một máy bất kỳ, các máy còn lại của S vẫn nối với nhau theo phần còn lại của vòng. Không có tập 5 máy nào an toàn, chẳng hạn với {1,2,3,6,7}, khi máy 1 bị tấn công thì máy 2 và máy 6 không còn liên lạc được.
5 6
1 2
2 3
3 1
3 4
4 5
5 3		 3 Ví dụ bổ sung (không có trong đề gốc). Hai vòng 1−2−3 và 3−4−5 chung máy 3. Mọi đường từ máy 1 sang máy 4 đều đi qua máy 3, nên S chỉ nằm trong một vòng.
4 4
1 2
2 1
2 3
3 4		 2 Ví dụ bổ sung (không có trong đề gốc). Hai dây cáp giữa máy 1 và máy 2 không giúp gì khi một máy bị tấn công. Tập {1,2} an toàn: nếu một trong hai máy bị tấn công thì chỉ còn một máy của S. Tập {1,2,3} không an toàn vì máy 2 bị tấn công thì máy 1 và máy 3 mất liên lạc.
2 0 1 Ví dụ bổ sung (không có trong đề gốc). Hai máy không có cáp nối nên không truyền được dữ liệu cho nhau, tập S chỉ gồm một máy.

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