โปรแกรมตรวจสอบว่าสามารถเรียนวิชาทั้งหมดได้หรือไม่ใน Python

สมมติว่ามีเมทริกซ์ 2D โดย matrix[i] แสดงรายการวิชาบังคับก่อนหน้าที่ต้องเรียนก่อนวิชา i ตอนนี้เราต้องตรวจสอบว่าสามารถเรียนวิชาทั้งหมดได้หรือไม่

เช่น ถ้าอินพุตคือ matrix = [[1],[2],[]] ผลลัพธ์จะเป็น True เนื่องจากเรียนวิชา 2 แล้ว 1 แล้ว 0 ได้

ขั้นตอนการแก้ปัญหา

• กำหนดฟังก์ชัน dfs() รับ i
  • ถ้า vis[i] เป็น true คืนค่า false
  • ถ้า chk[i] เป็น true คืนค่า True
  • vis[i] := True
  • สำหรับแต่ละ j ใน matrix[i] ถ้า dfs(j) เป็น false คืนค่า False
  • vis[i] := False, chk[i] := True คืนค่า True
• จากเมธอดหลัก
  • vis := รายการขนาดเท่าจำนวนแถวของ matrix เริ่มต้นทั้งหมด false
  • chk := รายการขนาดเท่าจำนวนแถวของ matrix เริ่มต้นทั้งหมด false
  • for i ในช่วง 0 ถึงจำนวนแถว ถ้า dfs(i) เป็น false คืนค่า False
  • คืนค่า True

ตัวอย่างโค้ด

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))

อินพุต

matrix = [ [1], [2], [] ]

เอาต์พุต

True