https://leetcode.com/problems/course-schedule-iv/description/
共有 numCourses
門課程,課程以 0
到 numCourses - 1
進行編號
你會得到一個陣列 prerequisites
,其中 prerequisites[i] = [ai, bi]
表示如果你想修課程 bi
,則必須先修過 ai
先修課程的條件也可以是間接的:
如果課程 a
是課程 b
的先修課程,且課程 b
是課程 c
的先修課程,那麼課程 a
也是課程 c
的先修課程
給定陣列 queries
,其中 queries[j] = [uj, vj]
對於第 j
個查詢,你需要回答課程 uj
是否為課程 vj
的先修課程
回傳一個布林陣列 answer
,其中 answer[j]
是第 j
個查詢的答案
這題有個關鍵句:
先修課程的條件也可以是間接的
這提示了我們,這題其實可以看作是解遞移閉包的問題
怎麼說?
Let the courses be represented as a set of integers
Define a binary relation :
題目給定的 prerequisites
就可理解為
For each pair , we have
何謂遞移包 () 呢?即 之最小子集合滿足遞移性:
你會發現這正對應了題目原文所說的:
If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.
所以這題我們用 Floyd-Warshall Algorithm 解
定義相鄰矩陣 :
遞迴關係式為:
其中 為 到 路徑上之中繼點