Chương trình kiểm tra có thể học hết tất cả khóa học không trong Python

Cho ma trận 2D matrix với matrix[i] là danh sách khóa học tiên quyết của khóa i. Kiểm tra xem có thể học hết tất cả khóa học không (không có chu trình phụ thuộc).

Ví dụ

Đầu vào: matrix = [[1],[2],[]].
Đầu ra: True (học khóa 2, rồi 1, rồi 0).

Thuật toán

1. Sử dụng DFS với hai mảng vis (đang thăm) và chk (đã xử lý).
2. Hàm dfs(i):
   • Nếu vis[i] true -> chu trình, trả về False.
   • Nếu chk[i] true -> đã an toàn, trả về True.
   • Đánh dấu vis[i]=True.
   • Duyệt các tiên quyết j trong matrix[i], nếu dfs(j) false thì trả về False.
   • Đánh dấu vis[i]=False, chk[i]=True, trả về True.
3. Gọi dfs(i) cho mọi i, nếu bất kỳ cái nào false thì trả về False.
4. Trả về True.

Mã nguồn Python

class Solution:
    def solve(self, matrix):
        vis = [False for _ in matrix]
        chk = [False for _ in matrix]
        def dfs(i):
            if vis[i]: return False
            if chk[i]: return True
            vis[i] = True
            for j in matrix[i]:
                if not dfs(j):
                    return False
            vis[i] = False
            chk[i] = True
            return True
        for i in range(len(matrix)):
            if not dfs(i):
                return False
        return True

ob = Solution()
matrix = [[1], [2], []]
print(ob.solve(matrix))

Đầu vào / Đầu ra

Input: matrix = [[1], [2], []]
Output: True