Ứng dụng DFS: kiểm tra quan hệ tiên quyết

Trong mô hình của SGK, cạnh i→j nghĩa là **muốn học i thì phải học j trước**. Dữ liệu mẫu có 1→0,2→0,3→1,3→2,4→3. Có thể học 0, rồi 1 và 2, rồi 3, rồi 4; hệ thống không mâu thuẫn. Nếu thêm 0→4, các yêu cầu tạo vòng 0→4→3→1→0: muốn học một phần lại phải hoàn thành các phần cuối cùng quay về chính nó. Hệ thống có thể hoàn thành mọi chuyên đề theo các ràng buộc này khi đồ thị có hướng **không có chu trình**, giả định không có ràng buộc nào khác.

state=0 là chưa bắt đầu, 1 là đang nằm trên nhánh DFS hiện tại, 2 là đã duyệt xong. Gặp cạnh tới state=1 tạo đường quay về một đỉnh đang ở nhánh hiện tại, nên phát hiện chu trình. Gặp state=2 chưa đủ để kết luận có chu trình. active lưu nhánh hiện tại. Hàm trả một danh sách đỉnh tạo chu trình, có lặp đỉnh đầu ở cuối để khép vòng; trả [] nếu không có. Phải xét cả các đỉnh chưa tới được từ lượt đầu. ```python def cycle_visit(Adj, u, state, active): state[u] = 1 active.append(u) for v in Adj[u]: if state[v] == 1: return active[active.index(v):] + [v] if state[v] == 0: cycle = cycle_visit(Adj, v, state, active) if cycle: return cycle active.pop() state[u] = 2 return [] def directed_cycle(Adj): state = [0]*len(Adj) active = [] for u in range(len(Adj)): if state[u] == 0: cycle = cycle_visit(Adj, u, state, active) if cycle: return cycle return [] ```