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] Tính khả thi của sắp xếp topo

    Cho đồ thị có hướng nnn đỉnh và mmm cung. Hãy kiểm tra xem có tồn tại một thứ tự topo (sắp xếp tô-pô) hay không — điều này tương đương với đồ thị không có chu trình có hướng (là DAG).

    • Đị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ố u vu\ vu v nghĩa là có 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\cdot 10^50≤m≤2⋅105.

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

      In YES nếu tồn tại sắp xếp topo (đồ thị là DAG), ngược lại in NO.

    Ví dụ:

    Đầu vào:

    3 2
1 2
2 3

    Đầu ra:

    YES

    Giải thích:

    Cung 1->2->3 khong tao chu trinh -> ton tai sap xep topo 1,2,3 -> YES.

    Đang tải editor...