力扣1462. 课程表 IV

力扣1462. 课程表 IV

题目

题目解析及思路

题目要求判断query中每组询问是否正确

判断是否先决，拓扑排序 + 所有先决条件都存在二维数组中，询问直接调用

代码

class Solution {
public:vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& pre, vector<vector<int>>& queries) {vector<int> d(n, 0); // 入度数组vector<vector<int>> g(n); // 邻接表vector<vector<bool>> prerequisites(n, vector<bool>(n, false)); // prerequisites[v][u] 表示 u 是否是 v 的先修课程// 构建图和入度数组for (const auto& p : pre) {int u = p[0], v = p[1];g[u].push_back(v);d[v]++;}queue<int> q;// 所有入度为 0 的课程入队for (int i = 0; i < n; i++) {if (d[i] == 0) {q.push(i);}}// 拓扑排序while (!q.empty()) {int u = q.front();q.pop();for (int v : g[u]) {// 将 u 的先修课程传递给 v//比常规的拓扑多这一步:传递for (int i = 0; i < n; i++) {if (prerequisites[u][i]) {prerequisites[v][i] = true;}}// u 本身也是 v 的先修课程prerequisites[v][u] = true;// 入度减 1d[v]--;if (d[v] == 0) {q.push(v);}}}// 处理查询vector<bool> res;for (const auto& query : queries) {int u = query[0], v = query[1];res.push_back(prerequisites[v][u]);}return res;}
};