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

    solution

    Đề bài: [Hệ điều hành Unix] Truy vết chu trình phụ thuộc

    Truy vết chu trình phụ thuộc

    Khi systemd báo lỗi phụ thuộc vòng tròn, admin cần biết chu trình cụ thể để gỡ. Hãy tìm một chu trình trong đồ thị phụ thuộc (A B = A khởi động trước B) và in ra.

    Để kết quả xác định: duyệt DFS bắt đầu từ các đỉnh theo thứ tự bảng chữ cái, và tại mỗi đỉnh xét các hàng xóm theo thứ tự bảng chữ cái. Chu trình tìm thấy đầu tiên được in.

    • Nếu không có chu trình: in OK.
    • Nếu có: in CYCLE, dòng sau là chu trình dạng x -> y -> ... -> x.

    Ví dụ

    a b, b a → CYCLE rồi a -> b -> a.

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

      Dòng đầu là n, sau đó n dòng tên dịch vụ. Dòng tiếp là m, sau đó m dòng A B (A trước B).

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

      1 ≤ n ≤ 100. Cạnh có thể trùng nhưng không có self-loop.

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

      OK nếu không có chu trình. Ngược lại CYCLE rồi một dòng mô tả chu trình x -> ... -> x.

    Ví dụ:

    Đầu vào:

    2
a
b
2
a b
b a

    Đầu ra:

    CYCLE
a -> b -> a

    Giải thích:

    a trước b và b trước a tạo chu trình; DFS từ a tìm thấy a -> b -> a.

    Đang tải editor...