Trong lý thuyết đồ thị, một thành phần liên thông của một đồ thị vô hướng là một đồ thị con trong đó giữa bất kì hai đỉnh nào đều có đường đi đến nhau, và không thể nhận thêm bất kì một đỉnh nào mà vẫn duy trì tính chất trên. Cho một đồ thị vô hướng gồm N nút và M cạnh. Các nút được đánh số từ 1 đến N. Nhiệm vụ của bạn là tìm số lượng thành phần liên thông trong đồ thị
Input
Dòng đầu tiên gồm 2 số nguyên N và M biểu thị số lượng nút và số cạnh trong đồ thị.
M dòng tiếp theo gồm 2 số nguyên a và b biểu thị một kết nối giữa nút a và nút b.
Output:
Đưa ra một số nguyên duy nhất biểu thị số lượng thành phần liên thông trong đồ thị
Giới hạn:
1<=N<=10^5
1<=M<=10^5
Input | Output |
10 10 7 10 9 2 9 10 4 8 5 6 4 3 3 7 8 4 5 7 8 7 6 |
2 |
10 9 7 10 9 2 9 10 4 8 5 6 4 3 3 7 8 4 8 7 6 |
3 |