Bình luận

• 
  

  -1

  vanphukhang_0604    12:06 a.m. 19 Tháng 8, 2023 ← chỉnh sửa 3 →

  CSES - Flight Route Requests | Yêu cầu đường bay

  Có \(n\) thành phố với các sân bay nhưng không có các chuyến bay nối giữa chúng. Bạn được đưa \(m\) yêu cầu về các tuyến đường bay.

  Nhiệm vụ của bạn là xác định số lượng chuyến bay một chiều tối thiểu để có thể thoả mãn tất cả các yêu cầu.

  Input

  • Dòng đầu tiên chứa hai số nguyên \(n \ (1 \leq n \leq 10^5)\) và \(m \ (1 \leq m \leq 2 \cdot 10^5)\): số lượng thành phố và số yêu cầu. Các thành phố được đánh số \(1, 2, \ldots, n\).
  • \(m\) dòng tiếp theo mô tả các yêu cầu. Mỗi dòng có hai số nguyên \(a\) và \(b \ (1 \leq a, b \leq n)\): phải có một tuyến đường từ thành phố \(a\) đến thành phố \(b\). Mỗi yêu cầu là độc nhất.

  Output

  • In ra một số nguyên là số lượng chuyến bay tối thiểu.

  Example

  Test 1

  Input

  4 5
  1 2
  2 3
  2 4
  3 1
  3 4

  Output

  4

  Note

  Giải thích: Bạn có thể nối các chuyến bay từ các thành phố \(1 \rightarrow 2\), \(2 \rightarrow 3\), \(2 \rightarrow 4\) và \(3 \rightarrow 1\). Sau đó bạn có thể bay từ thành phố \(3\) đến thành phố \(4\) bằng tuyến đường \(3 \rightarrow 1 \rightarrow 2 \rightarrow 4\).