2023-09-12力扣每日一题

链接：

1462. 课程表 IV

题意

一个pair表示a是b的前置

进行n次查询，查询q是否是p的前置（可以不是直接前置）

解：

就是要把01、12、13这种能转换出02、03，弗洛伊德即可

无环无负权

实际代码：

#include
using namespace std;
vector checkIfPrerequisite(int numCourses, vector>& prerequisites, vector>& queries)
{
	vector>edges(numCourses+3,vector(numCourses+3));
	for(auto prerequisite:prerequisites) edges[prerequisite[0]][prerequisite[1]]=1;
	for(int i=0;ians;
	for(auto querie:queries)
	{
		if(edges[querie[0]][querie[1]]<0x3f3f3f3f) ans.push_back(true);
		else ans.push_back(false);
	}
	return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

限制：

• 2 <= numCourses <= 100
• 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
• prerequisites[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• 每一对 [ai, bi] 都 不同
• 先修课程图中没有环。
• 1 <= queries.length <= 104
• 0 <= ui, vi <= n - 1
• ui != vi