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 cạnh của bao đóng bắc cầu

    Cho quan hệ hai ngôi trên tập {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1} biểu diễn bằng các cặp có hướng (u,v)(u,v)(u,v). Hãy tính bao đóng bắc cầu của quan hệ (thuật toán Warshall) và đếm số cặp (u,v)(u,v)(u,v) thuộc bao đóng (tức số cạnh có hướng, kể cả khuyên nếu phát sinh do chu trình).

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

      Dòng đầu: nnn, mmm. mmm dòng sau mỗi dòng một cặp u vu\ vu v (0≤u,v<n0\le u,v<n0≤u,v<n).

    • Ràng buộc đầu vào:

      1≤n≤4001 \le n \le 4001≤n≤400, 0≤m≤n20 \le m \le n^20≤m≤n2.

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

      Một dòng: số cặp (u,v)(u,v)(u,v) trong bao đóng bắc cầu.

    Ví dụ:

    Đầu vào:

    3 2
0 1
1 2

    Đầu ra:

    3

    Giải thích:

    Từ các cạnh $0\to1,1\to2$ suy ra thêm $0\to2$; bao đóng có 3 cặp.

    Đang tải editor...