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] Phân hoạch từ quan hệ tương đương

    Cho một quan hệ tương đương trên {1,…,n}\{1, \dots, n\}{1,…,n} được sinh bởi mmm cặp (đảm bảo phản xạ, đối xứng, bắc cầu qua bao đóng). Quan hệ tương đương phân hoạch tập thành các lớp tương đương.

    Hãy in hai số: số lớp tương đương và kích thước của lớp lớn nhất.

    • Đị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ố a ba\ ba b nghĩa là aaa và bbb cùng lớp.

    • 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:

      Hai số nguyên cách nhau dấu cách: số lớp tương đương và kích thước lớp lớn nhất.

    Ví dụ:

    Đầu vào:

    5 2
1 2
2 3

    Đầu ra:

    3 3

    Giải thích:

    Lop {1,2,3} va hai lop don {4},{5} -> 3 lop, lop lon nhat kich thuoc 3.

    Đang tải editor...