Học ngôn ngữ
Đề bài
Mô tả
Một công ty có nhân viên và ngôn ngữ chính thức, được đánh số từ đến . 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 đồ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 và : số nhân viên và số ngôn ngữ.
- dòng tiếp theo mô tả danh sách ngôn ngữ của từng nhân viên. Dòng thứ bắt đầu bằng số nguyên : số ngôn ngữ mà nhân viên biết, tiếp theo là số nguyên : đị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
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