Không hỗ trợ Mobile

Chế độ luyện tập yêu cầu môi trường màn hình lớn để làm bài và chống gian lận hiệu quả. Vui lòng truy cập bằng máy tính (Desktop/Laptop) để tiếp tục thao tác.

Quay lại trang chủ

#1033 · UMTN 2022 - Cố vấn học tập

MÔ TẢ BÀI TOÁN

Khi trở thành Tân sinh viên K22 Khoa Công Nghệ Thông Tin – Đại học Công nghệ TP.HCM (HUTECH), các sinh viên và tập thể lớp được yêu cầu cao về sự độc lập, chủ động trong xây kế hoạch cho tất cả công việc liên quan đến quá trình học tập và sinh hoạt của mình trong suốt thời gian học. Trong quá trình học tập, nếu sinh viên có khó khăn hoặc chưa định hướng được các vấn đề liên quan đến kế hoạch học tập, định hướng chuyên ngành,… thì đã đội ngũ Thầy/Cô giáo của Khoa, đặc biệt là Quý Thầy/Cô Cố Vấn học Tập (CVHT) sẽ luôn đồng hành cùng các bạn.

Với một lớp gồm N sinh viên (từ 1 đến N), ở những buổi đầu của học kì I năm thứ 1, CVHT rất khó khăn để có thể truyền tải được các nội dung quan trọng tới toàn bộ sinh viên của lớp. Giả sử thầy Trung có một thông tin rất quan trọng cần thông báo tới tất cả các sinh viên trong lớp. Để tiết kiệm thời gian, thầy Trung chỉ nhắn tin tới 1 số bạn Sinh viên, các bạn Sinh viên nhận được thông tin sẽ tiếp tục chuyển tiếp nội dung này cho tất cả các bạn mà có thể liên lạc được. Quá trình được tiếp tục lặp lại cho đến khi tất cả Sinh viên trong lớp đều nhận được thông tin.

Yêu cầu: Cho biết số lượng Sinh viên ít nhất mà thầy Trung cần nhắn tin để thông tin có thể tới được cả lớp.

Dữ liệu vào

  • Dòng 1: Số nguyên N và K cách nhau bằng kí tự khoảng trắng. N là số lượng sinh viên của lớp và K là tổng số dòng thể hiện các sinh viên có thể liên hệ được cho nhau.
  • K dòng tiếp theo: Mỗi dòng gồm 2 số nguyên dương i và j (cách nhau khoảng trắng): cho biết Sinh viên i có thể liên hệ được với sinh viên j (và ngược lại SV j cũng có thể liên hệ được sinh viên i). Điều kiện:
  • 1 \leqslant N, K \leqslant 10^9.
  • 1 \leqslant i, j \leqslant N

Dữ liệu ra

Một dòng duy nhất ghi một số nguyên là số lượng Sinh viên ÍT NHẤT cần tìm.

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
T
Đoàn Chí Tân @2180607068
0 ms 224 KB
514 Bytes
23/09/2025
15:51
2
C
Sơn Trung Chiến @25800600077
1 ms 228 KB
713 Bytes
27/12/2025
23:07
3
C
Huỳnh Lê Quốc Cường @24800600137
1 ms 228 KB
879 Bytes
15/03/2025
09:57
4
K
Nguyễn Võ Lê Khoa @2380601073
1 ms 232 KB
915 Bytes
20/05/2025
08:47
5
Q
Trần Nhật Quang @25800600554
1 ms 244 KB
2375 Bytes
25/12/2025
17:08
6
T
Trần Ngọc Tân @2280602874
1 ms 248 KB
1652 Bytes
23/09/2023
21:42
7
P
Khương Gia Phát @24800612880
1 ms 260 KB
1953 Bytes
23/05/2025
08:28
8
S
Nguyễn Võ Hoàng Sơn @2280618566
1 ms 268 KB
1115 Bytes
24/10/2023
02:29
9
B
Trần Gia Bảo @2380600172
1 ms 268 KB
1507 Bytes
01/10/2024
20:54
10
T
Đinh Cao Toàn @2180608111
1 ms 284 KB
616 Bytes
14/05/2023
20:50
11
T
Nguyễn Đức Tân @2187701108
1 ms 288 KB
516 Bytes
25/03/2023
18:03
12
L
Phạm Khắc Duy Long @2280610603
1 ms 288 KB
725 Bytes
26/08/2023
19:05
13
L
Phạm Khắc Duy Long @2280610603
1 ms 288 KB
725 Bytes
26/08/2023
22:00
14
Đ
Nguyễn Tiến Đạt @2380600453
1 ms 288 KB
859 Bytes
23/11/2025
22:00
15
K
Nguyễn Anh Khoa @2380601059
1 ms 292 KB
863 Bytes
21/11/2024
03:33
16
L
Phạm Khắc Duy Long @2280610603
1 ms 296 KB
752 Bytes
25/11/2022
20:40
17
K
Nguyễn Anh Khoa @2380601059
1 ms 296 KB
762 Bytes
18/11/2024
02:12
18
T
Nguyễn Công Tiến @2380605702
1 ms 296 KB
782 Bytes
07/11/2023
12:49
19
K
Nguyễn Anh Khoa @2380601059
1 ms 296 KB
905 Bytes
18/11/2024
01:28
20
K
Trần Tuấn Kiệt @2380601166
1 ms 300 KB
716 Bytes
26/09/2024
08:23

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

Chưa có thảo luận nào cho bài này.

GỢI Ý & HƯỚNG DẪN

SV 1 có thể liên hệ được với SV 2 và, SV 2 có thể liên hệ được với SV 1, 3. SV 3 có thể liên hệ được với SV 2, 4 và SV 4 có thể liên hệ được với SV 3. SV 5 có thể liên hệ được với SV 7, 6 và SV 6 có thể liên hệ được với SV 5. SV 7 có thể liên hệ được với SV 5. SV 8 có thể liên hệ được với SV 9 và SV 9 có thể liên hệ được với SV 8. Như vậy, Thầy Trung chỉ cần gửi tin nhắn tới 4 SV (VD: 1, 5, 8, 10).

Viết code