trang chủ / bài tập / learnlang

Học ngôn ngữ

Đề bài

Mô tả

Một công ty có n nhân viên và m ngôn ngữ chính thức, được đánh số từ 1 đến m. Với mỗi nhân viên, ta biết danh sách các ngôn ngữ mà người đó biết (danh sách này có thể rỗng).

Hai nhân viên có thể trao đổi thư từ với nhau nếu họ cùng biết một ngôn ngữ, hoặc gián tiếp thông qua những nhân viên khác làm trung gian dịch (ví dụ A và B cùng biết ngôn ngữ 1, B và C cùng biết ngôn ngữ 2, thì A và C có thể liên lạc qua B).

Mỗi nhân viên có thể học thêm ngôn ngữ. Học một ngôn ngữ cho một nhân viên tốn 1 đồng. Hãy tìm số tiền nhỏ nhất công ty cần chi để cuối cùng mọi cặp nhân viên đều có thể trao đổi thư từ với nhau (trực tiếp hoặc gián tiếp).

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên nm: số nhân viên và số ngôn ngữ.
  • n dòng tiếp theo mô tả danh sách ngôn ngữ của từng nhân viên. Dòng thứ i bắt đầu bằng số nguyên ki: số ngôn ngữ mà nhân viên i biết, tiếp theo là ki số nguyên aij: định danh các ngôn ngữ đó. Các định danh trong cùng một dòng là phân biệt.

Dữ liệu ra

In ra một số nguyên duy nhất: số tiền nhỏ nhất cần chi.

Ràng buộc

  • 2n,m100
  • 0kim
  • 1aijm

Ví dụ

Input Output Giải thích
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
0 Mọi nhân viên đã liên thông qua chuỗi ngôn ngữ 2-3-4-5, không cần học thêm.
8 7
0
3 1 2 3
1 1
2 5 4
2 6 7
1 3
2 7 4
1 1
2 Nhân viên 1 học ngôn ngữ 2 và nhân viên 8 học ngôn ngữ 4 là đủ để mọi người liên thông.
2 2
1 2
0
1 Nhân viên 2 chưa biết ngôn ngữ nào nên phải học ngôn ngữ 2.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0