CSES - Flight Route Requests | Yêu Cầu Đường Bay

Xem PDF
Tác giả:
ngpin_04
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có \(n\) thành phố với các sân bay nhưng không có kết nối chuyến bay. Bạn được cho \(m\) yêu cầu những tuyến đường nào có thể đi được.

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

Input

Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và yêu cầu. Các thành phố được đánh số \(1, 2, \ldots, n\).

Sau đó, có \(m\) dòng mô tả các yêu cầu. Mỗi dòng có hai số nguyên \(a\) và \(b\): 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à duy nhất.

Output

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

Constraints

  • \(1 \leq n \leq 10 ^ 5\)
  • \(1 \leq m \leq 2 \cdot 10 ^ 5\)
  • \(1 \leq a, b \leq n\)

Example

Input:

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

Output:

4

Explanation: Bạn có thể tạo các kết nối \(1 \rightarrow 2\), \(2 \rightarrow 3\), \(2 \rightarrow 4\) và \(3 \rightarrow 1\). Sau đó, bạn cũng có thể bay từ thành phố \(3\) đến thành phố \(4\) bằng cách sử dụng tuyến đường \(3 \rightarrow 1 \rightarrow 2 \rightarrow 4\).

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\).