Nhóm bạn trong trường
Thời gian
1s
Bộ nhớ
1GB
Đọc vào (Input)
GROUPS.INP
Ghi ra (Output)
GROUPS.OUT
Đề bài
Trong một trường học có n học sinh được đánh số từ 1 đến n. Nhà trường có danh sách m mối quan hệ quen biết giữa các học sinh. Mỗi mối quan hệ gồm hai số u và v, nghĩa là học sinh u quen học sinh v. Nếu học sinh A quen học sinh B, và học sinh B quen học sinh C, thì cả A, B, C được xem là thuộc cùng một nhóm bạn, dù A và C có thể không quen trực tiếp nhau.
Yêu cầu: Hãy đếm xem trong trường có tất cả bao nhiêu nhóm bạn riêng biệt.
Dữ liệu vào: Đọc từ tệp văn bản GROUPS.INP gồm:
- Dòng đầu tiên gồm hai số nguyên n, m — số học sinh và số mối quan hệ quen biết.
- m dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v, cho biết học sinh u quen học sinh v.
Dữ liệu ra: Ghi ra tệp văn bản GROUPS.OUT gồm:
- Một số nguyên duy nhất là số lượng nhóm bạn riêng biệt trong trường.
Giới hạn
- 1 ≤ n, m ≤ 105.
- 1 ≤ u, v ≤ n.
- Các mối quan hệ là hai chiều, tức là nếu u quen v thì v cũng quen u.
Ví dụ
Input 1
5 4 1 2 1 3 2 3 4 5
Output 1
2
Ràng buộc & Tóm tắt
Giải thích
Có 5 học sinh và 4 mối quan hệ quen biết. Ta chia được thành hai nhóm:
- Nhóm 1 gồm học sinh 1, 2, 3.
- Nhóm 2 gồm học sinh 4, 5.
Vì vậy có tất cả 2 nhóm bạn riêng biệt.
Subtask
- Subtask 1 (30% số điểm): 1 ≤ n, m ≤ 100.
- Subtask 2 (30% số điểm): 1 ≤ n, m ≤ 5000.
- Subtask 3 (40% số điểm): 1 ≤ n, m ≤ 105.
Thông tin bài tập
Mã bài:
GROUPS
Mức độ:
Bình thường
Điểm số:
90 đ