Thêm ít cạnh nhất để đồ thị liên thông mạnh

Buổi 43 — SCC (Tarjan) & 2-SAT Buổi 69-70 — Mock Tổng hợp Graphs
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.

Draft saved