Đếm thành phần dạng cây

Buổi 24 — Mock Contest Phase 1
Points
21
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh (có thể có cạnh song song hoặc khuyên).

Một thành phần liên thông được gọi là cây nếu nó không chứa bất kỳ chu trình nào (tức là số cạnh đúng bằng số đỉnh trừ $1$, không có khuyên hay cạnh song song).

Hãy đếm số lượng thành phần liên thông là cây trong đồ thị đã cho.

Dữ liệu vào
  • Dòng đầu 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$).
Dữ liệu ra
  • Một số nguyên duy nhất là số lượng thành phần liên thông là cây.
Ví dụ
Input Output
6 5
1 2
2 3
3 1
4 5
5 6
1
4 0 4
Giới hạn
  • $1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Draft saved