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 đỉnh khớp

    Cho đồ thị vô hướng gồm nnn đỉnh và mmm cạnh. Một đỉnh khớp (articulation point) là đỉnh mà khi xoá nó (cùng các cạnh kề) thì số thành phần liên thông của đồ thị tăng lên.

    Hãy đếm số đỉnh khớp.

    Ví dụ: Đường thẳng 1 ⁣− ⁣2 ⁣− ⁣31\!-\!2\!-\!31−2−3 có đỉnh 222 là đỉnh khớp duy nhất (xoá 222 tách 111 và 333).

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

      Dòng đầu chứa nnn và mmm. mmm dòng tiếp theo, mỗi dòng hai số u vu\ vu v là một cạnh. Có thể có cạnh lặp và khuyên (khuyên bỏ qua).

    • 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, 1≤u,v≤n1 \le u, v \le n1≤u,v≤n.

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

      In ra một số nguyên là số đỉnh khớp.

    Ví dụ:

    Đầu vào:

    3 2
1 2
2 3

    Đầu ra:

    1

    Giải thích:

    Đồ thị là đường thẳng 1-2-3. Xoá đỉnh 2 làm 1 và 3 không còn liên thông nên 2 là đỉnh khớp. Xoá 1 hoặc 3 không tách đồ thị. Vậy có 1 đỉnh khớp.

    Đang tải editor...