Đếm cụm đảo kết nối

Buổi 18 — BFS & DFS
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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$.
Draft saved