สมมติว่าเรามีเมทริกซ์ 2 มิติ โดยที่ matrix[i] แทนรายชื่อวิชาบังคับก่อนที่จำเป็นสำหรับการลงทะเบียนหลักสูตร i ตอนนี้ต้องเช็คก่อนว่าจะลงได้ทุกวิชาหรือไม่
ดังนั้น หากอินพุตเป็นเหมือนเมทริกซ์ =[1],[2],[]] ผลลัพธ์จะเป็น True เนื่องจากเราสามารถเรียนคอร์สที่ 2 ต่อด้วยคอร์ส 1 และคอร์ส 0
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน dfs() นี่จะใช้เวลาฉัน
-
ถ้า vis[i] เป็นจริง แล้ว
-
คืนค่าเท็จ
-
-
ถ้า chk[i] เป็นจริง แล้ว
-
คืนค่า True
-
-
vis[i]:=จริง
-
สำหรับแต่ละ j ในเมทริกซ์[i] ทำ
-
ถ้า dfs(j) เป็นเท็จ แล้ว
-
คืนค่าเท็จ
-
-
-
vis[i]:=เท็จ
-
chk[i]:=จริง
-
คืนค่า True
-
จากวิธีหลัก ให้ทำดังนี้ −
-
vis:=รายการขนาดเท่ากับจำนวนแถวของเมทริกซ์และเริ่มต้นทั้งหมดเป็นเท็จ
-
chk:=รายการขนาดเท่ากับจำนวนแถวของเมทริกซ์และเริ่มต้นทั้งหมดเป็นเท็จ
-
สำหรับฉันในช่วง 0 ถึงจำนวนแถวของเมทริกซ์ ทำ
-
ถ้า dfs(i) เป็นเท็จ แล้ว
-
คืนค่าเท็จ
-
-
-
คืนค่า 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
