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

    solution

    Đề bài: [Giải thuật] Đếm số cầu trong đồ thị vô hướng

    Cho đồ thị vô hướng đơn nnn đỉnh, mmm cạnh. Một cầu là cạnh mà khi xóa đi làm tăng số thành phần liên thông. Hãy đếm số cầu.

    Giả thiết không có cạnh song song trùng lặp.

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

      Dòng đầu: nnn, mmm. mmm dòng: uuu, vvv.

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

      1≤n≤1051 \le n \le 10^51≤n≤105, 0≤m≤2⋅1050 \le m \le 2\cdot10^50≤m≤2⋅105.

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

      Một số nguyên: số cầu.

    Ví dụ:

    Đầu vào:

    5 4
1 2
2 3
3 4
4 5

    Đầu ra:

    4

    Giải thích:

    Đồ thị là đường thẳng 1-2-3-4-5; mọi cạnh đều là cầu nên đáp án 4.

    Đang tải editor...