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] Bao đóng phản xạ - đối xứng - bắc cầu

    Cho quan hệ hai ngôi RRR trên tập {1,…,n}\{1, \dots, n\}{1,…,n} gồm mmm cặp có thứ tự. Hãy tính bao đóng của RRR lần lượt qua ba tính chất: phản xạ, đối xứng, rồi bắc cầu (bao đóng tương đương). Sau bao đóng, hãy đếm tổng số cặp có thứ tự (a,b)(a, b)(a,b) thuộc quan hệ kết quả.

    Gợi ý: bao đóng phản xạ + đối xứng + bắc cầu của một quan hệ chính là quan hệ tương đương sinh bởi RRR; mỗi lớp tương đương kích thước sss đóng góp s2s^2s2 cặp.

    • Đị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 là một cặp thuộc RRR.

    • 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ố cặp sau bao đóng.

    Ví dụ:

    Đầu vào:

    4 2
1 2
3 4

    Đầu ra:

    8

    Giải thích:

    Hai lop tuong duong {1,2} va {3,4}, moi lop dong gop $2^2=4$ cap -> tong $8$.

    Đang tải editor...