# LeetCode 1462. Course Schedule IV

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` 個查詢的答案

## 思考

這題有個關鍵句：
**先修課程的條件也可以是間接的**

這提示了我們，這題其實可以看作是解[遞移閉包](https://hackmd.io/@RyoukiWei/graph_2#Transtive-Closure)的問題

怎麼說？

Let the courses $C$ be represented as a set of integers $\left\{0, 1, \cdots , n-1\right\}$
Define a binary relation $R\subseteq C\times C$: $(a, b)\in R \Leftrightarrow \text{course } a \text{ is a prereqisites for course } b.$

題目給定的 `prerequisites` 就可理解為
For each pair $\left[ a,b \right]\in\mathrm{prerequisites}$, we have $(a,b)\in R$

何謂遞移包 ($R^+$) 呢？即 $R$ 之最小子集合滿足遞移性：
$\text{If }(a,b)\in R^+ \text{and } (b,c)\in R^+, \text{then } (a, c)\in 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\left\lbrack i \right\rbrack \left\lbrack j \right\rbrack =
\begin{cases}
1 &&\text{ if }(i,j)\in R\\
0 &&\text{ otherwise}
\end{cases}
$$

遞迴關係式為：

$$
T_{ij} = T_{ij}\vee (T_{ik}\wedge T_{kj})
$$

其中 $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
}