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

    solution

    Đề bài: [Giải thuật] Phát hiện chu trình trong đồ thị có hướng

    Cho đồ thị có hướng nnn đỉnh, mmm cung. Hãy xác định đồ thị có chứa chu trình có hướng hay không.

    • Đị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.

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

      In YES nếu có chu trình, ngược lại NO.

    Ví dụ:

    Đầu vào:

    3 3
1 2
2 3
3 1

    Đầu ra:

    YES

    Giải thích:

    Tồn tại chu trình 1->2->3->1 nên in YES.

    Đang tải editor...