Try   HackMD

LeetCode 1462. Course Schedule IV

https://leetcode.com/problems/course-schedule-iv/description/

題目大意

共有 numCourses 門課程,課程以 0numCourses - 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

C be represented as a set of integers
{0,1,,n1}

Define a binary relation
RC×C
:
(a,b)Rcourse a is a prereqisites for course b.

題目給定的 prerequisites 就可理解為
For each pair

[a,b]prerequisites, we have
(a,b)R

何謂遞移包 (

R+) 呢?即
R
之最小子集合滿足遞移性:
If (a,b)R+and (b,c)R+,then (a,c)R+

你會發現這正對應了題目原文所說的:

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 解

定義相鄰矩陣

T

T[i][j]={1 if (i,j)R0 otherwise

遞迴關係式為:

Tij=Tij(TikTkj)

其中

k
i
j
路徑上之中繼點

C++ 參考解答

class Solution
{
public:
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>> &prerequisites, vector<vector<int>> &queries)
    {
        vector<bool> ans;
        vector<vector<bool>> isPrereqisite(numCourses, vector<bool>(numCourses));

        for (const auto &prereqisite : prerequisites)
        {
            const int u = prereqisite[0];
            const int v = prereqisite[1];
            isPrereqisite[u][v] = true;
        }

        for (int k = 0; k < numCourses; ++k)
        {
            for (int i = 0; i < numCourses; ++i)
            {
                if (!isPrereqisite[i][k])
                    continue;
                for (int j = 0; j < numCourses; ++j)
                {
                    isPrereqisite[i][j] = isPrereqisite[i][j] || (isPrereqisite[i][k] && isPrereqisite[k][j]);
                }
            }
        }

        ans.reserve(queries.size());
        for (const auto &query : queries)
        {
            const int u = query[0];
            const int v = query[1];
            ans.push_back(isPrereqisite[u][v]);
        }

        return ans;
    }
};

Go 參考解答

func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
	isPrerequisite := make([][]bool, numCourses)
	for i := 0; i < numCourses; i++ {
		isPrerequisite[i] = make([]bool, numCourses)
	}
	for _, prereq := range prerequisites {
		u, v := prereq[0], prereq[1]
		isPrerequisite[u][v] = true
	}

	for k := 0; k < numCourses; k++ {
		for i := 0; i < numCourses; i++ {
			if !isPrerequisite[i][k] {
				continue
			}
			for j := 0; j < numCourses; j++ {
				isPrerequisite[i][j] = isPrerequisite[i][j] || isPrerequisite[i][k] && isPrerequisite[k][j]
			}
		}
	}

	ans := make([]bool, len(queries))
	for i, query := range queries {
		u, v := query[0], query[1]
		ans[i] = isPrerequisite[u][v]
	}

	return ans
}