Thêm ít cạnh nhất để đồ thị liên thông mạnh
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị có hướng gồm $N$ đỉnh và $M$ cạnh. Hãy tìm số lượng cạnh có hướng ít nhất cần thêm vào đồ thị để cả đồ thị trở thành liên thông mạnh (từ mọi đỉnh đều có thể đi đến mọi đỉnh khác).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$.
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh có hướng từ $u$ đến $v$.
Dữ liệu ra
In ra một số nguyên duy nhất là số cạnh ít nhất cần thêm.
Ví dụ
| Input | Output |
|---|---|
| 4 3 1 2 2 3 3 4 |
1 |
Giới hạn
$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$.
Community Discussion