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ố uv, 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ù AC 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

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 đ

Ủng Hộ Phát Triển Hệ Thống

Sự đồng hành của bạn là nguồn động lực rất lớn giúp đội ngũ duy trì, nâng cấp tài nguyên hệ thống chấm bài (Judge Server) ngày một mạnh mẽ hơn.

Ngân Hàng Techcombank
20492731612
Chủ tài khoản: VAN CONG DUC