Kết nối mạng lưới toàn phần
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Mạng giao thông gồm $N$ ngã tư và $M$ đường một chiều. Chính quyền muốn bổ sung thêm một số đường một chiều mới sao cho từ bất kỳ ngã tư nào cũng có thể đi đến mọi ngã tư khác (đồ thị trở thành một thành phần liên thông mạnh).
Hãy tìm số lượng đường một chiều ít nhất cần bổ sung.
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ố $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
In ra số cạnh ít nhất cần thêm.
Ví dụ
| Input | Output |
|---|---|
| 4 3 1 2 2 3 3 4 |
1 |
| 3 3 1 2 2 3 3 1 |
0 |
Giới hạn
$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion