Kết nối mạng lưới toàn phần

General
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.

Draft saved