dothi2 - Đếm số thành phần liên thông
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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ênCho 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

Ví dụ

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

 

 

Back to Top