Cầu Nối Giữa Các Vương Quốc

Buổi 43 — SCC (Tarjan) & 2-SAT
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị có hướng gồm N đỉnh và M cạnh. Hãy tìm số cạnh tối thiểu cần thêm vào để đồ thị trở thành liên thông mạnh.

Nếu đồ thị đã liên thông mạnh, in 0.

Dữ liệu vào
  • Dòng đầu: hai số nguyên N và M (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000)
  • M dòng tiếp theo: u v
Dữ liệu ra
  • Một số nguyên: số cạnh tối thiểu cần thêm.
Ví dụ
Input Output
4 3

1 2 2 3 3 4 | 1 |

Giới hạn
  • 1 ≤ N ≤ 100000
  • 0 ≤ M ≤ 200000
Draft saved