Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Số cạnh của cây khung

    Một cây (tree) là đồ thị vô hướng liên thông và không có chu trình. Một tính chất cơ bản: cây có nnn đỉnh thì có đúng n−1n-1n−1 cạnh.

    Cây khung (spanning tree) của một đồ thị liên thông nnn đỉnh cũng có đúng n−1n-1n−1 cạnh.

    Cho số đỉnh nnn, hãy in số cạnh của cây khung. Quy ước: nếu n=0n=0n=0 thì in 000.

    Ví dụ: n=5n=5n=5 đỉnh → cây khung có 444 cạnh.

    • Định dạng đầu vào:

      Một dòng gồm một số nguyên nnn — số đỉnh.

    • Ràng buộc đầu vào:

      0≤n≤10180 \le n \le 10^{18}0≤n≤1018.

    • Định dạng đầu ra:

      Một dòng: số cạnh của cây khung.

    Ví dụ:

    Đầu vào:

    5

    Đầu ra:

    4

    Giải thích:

    Cây có $n$ đỉnh thì $n-1$ cạnh, vậy $5-1=4$.

    Đang tải editor...