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] Đếm thành phần liên thông

    Cho đồ thị vô hướng nnn đỉnh và mmm cạnh. Hãy đếm số thành phần liên thông của đồ thị bằng cấu trúc Disjoint Set Union (DSU).

    • Đị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 mô tả một cạnh.

    • 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\cdot 10^50≤m≤2⋅105.

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

      Một số nguyên là 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 nhom {1,2,3} va {4,5} lien thong -> 2 thanh phan.

    Đang tải editor...