Đếm cụm đảo kết nối
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Quần đảo Trường Sa có $N$ hòn đảo (đánh số từ $1$ đến $N$) và $M$ cây cầu hai chiều nối giữa các đảo. Hai đảo thuộc cùng một cụm nếu có thể đi từ đảo này đến đảo kia qua một số cây cầu. Hãy đếm số lượng cụm đảo (thành phần liên thông) của đồ thị.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$) mô tả một cây cầu nối đảo $u$ và đảo $v$.
Dữ liệu ra
- In ra một số nguyên duy nhất là số thành phần liên thông.
Ví dụ
| Input | Output |
|---|---|
| 5 3 1 2 2 3 4 5 |
2 |
| 4 0 | 4 |
Giới hạn
- $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion