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.

    Chủ đề

    🧮 Cấu trúc dữ liệu & Giải thuậtGiải thuật: Đồ thịGraphTất cả môn học

    Đang tải editor...