Phân vùng mạng cảm biến

Bối cảnh và bài toán

Một hệ thống giám sát công nghiệp gồm n cảm biến và m đường truyền hai chiều. Hai cảm biến được xem là cùng một vùng liên lạc nếu có thể truyền dữ liệu cho nhau qua một hoặc nhiều đường trung gian.

Yêu cầu

Hãy xác định số vùng liên lạc độc lập trong toàn mạng.

Input

Dòng đầu gồm n, m. Mỗi trong m dòng tiếp theo chứa hai số u, v mô tả một liên kết hai chiều.

Output

In ra một số nguyên là số thành phần liên thông.

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 2*10^5
• 1 <= u,v <= n, u != v ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

6 3
1 2
2 3
5 6

Output

3

Giải thích. Các cạnh tạo thành các nhóm nút không giao nhau; mỗi lần bắt đầu duyệt từ một nút chưa thăm tương ứng một thành phần mới.

Ví dụ 2

Input

4 0

Output

4

Giải thích. Các cạnh tạo thành các nhóm nút không giao nhau; mỗi lần bắt đầu duyệt từ một nút chưa thăm tương ứng một thành phần mới.

Gợi ý

Hãy bắt đầu bằng cách phân loại graph, mục tiêu truy vấn và constraints; sau đó đối chiếu với Decision Map của buổi học trước khi viết code.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.