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

    solution

    Đề bài: [Giải thuật] Số thành phần liên thông

    Cho đồ thị vô hướng nnn đỉnh (đánh số từ 111 đến nnn) và mmm cạnh. Hãy đếm số thành phần liên thông của đồ thị.

    Ví dụ: 5 đỉnh, các cạnh (1-2), (2-3), (4-5) tạo thành 2 thành phần: {1,2,3} và {4,5}.

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

      Dòng đầu chứa hai số nguyên nnn và mmm. mmm dòng sau, mỗi dòng hai số uuu vvv là một cạnh vô hướng.

    • 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\times10^50≤m≤2×105, 1≤u,v≤n1 \le u, v \le n1≤u,v≤n.

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

      In một số nguyên: số thành phần liên thông.

    Ví dụ:

    Đầu vào:

    5 3
1 2
2 3
4 5

    Đầu ra:

    2

    Giải thích:

    Hai thành phần: {1,2,3} và {4,5} nên đáp án là 2.

    Đang tải editor...