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

    solution

    Đề bài: [Giải thuật] Sắp xếp tô-pô từ điển nhỏ nhất

    Cho đồ thị có hướng không chu trình (DAG) gồm nnn đỉnh và mmm cung. Hãy in một thứ tự tô-pô. Nếu có nhiều thứ tự, in thứ tự từ điển nhỏ nhất (ưu tiên đỉnh có chỉ số nhỏ hơn ra trước khi đủ điều kiện).

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

      Dòng đầu nnn và mmm. mmm dòng sau mỗi dòng uuu vvv: cung u→vu \to vu→v.

    • 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\times10^50≤m≤2×105. Đảm bảo đồ thị là DAG.

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

      In nnn số là một hoán vị 1..n1..n1..n — thứ tự tô-pô từ điển nhỏ nhất, cách nhau bởi dấu cách.

    Ví dụ:

    Đầu vào:

    4 3
1 2
1 3
3 4

    Đầu ra:

    1 2 3 4

    Giải thích:

    Cả 1 không có cung vào nên ra trước; sau đó chọn đỉnh nhỏ nhất khả thi: 2, rồi 3, rồi 4.

    Đang tải editor...