Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Lập lịch học phần bằng sắp xếp topo (Kahn)

    Một chương trình gồm nnn học phần đánh số 0..n−10..n-10..n−1 và mmm ràng buộc tiên quyết u → v (học u trước v). Hãy in một thứ tự học hợp lệ bằng thuật toán Kahn, ưu tiên chọn học phần có chỉ số nhỏ nhất khi có nhiều lựa chọn cùng lúc.

    Lưu ý: đề đảm bảo không có chu trình.

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

      Dòng 1: n mn\ mn m. mmm dòng tiếp theo: u v.

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

      1≤n≤2001 \le n \le 2001≤n≤200, 0≤m≤n(n−1)/20 \le m \le n(n-1)/20≤m≤n(n−1)/2.

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

      Một dòng nnn số là thứ tự topo hợp lệ.

    Ví dụ:

    Đầu vào:

    4 3
0 1
1 2
2 3

    Đầu ra:

    0 1 2 3

    Giải thích:

    Chuỗi 0→1→2→3 là thứ tự duy nhất.

    Đang tải editor...