课程表 IV【LC1462】
你总共需要上
numCourses门课，课程编号依次为0到numCourses-1。你会得到一个数组prerequisite，其中prerequisites[i] = [ai, bi]表示如果你想选bi课程，你 必须 先选ai课程。
- 有的课会有直接的先修课程，比如如果想上课程
1，你必须先上课程0，那么会以[0,1]数对的形式给出先修课程数对。先决条件也可以是 间接 的。如果课程
a是课程b的先决条件，课程b是课程c的先决条件，那么课程a就是课程c的先决条件。你也得到一个数组
queries，其中queries[j] = [uj, vj]。对于第j个查询，您应该回答课程uj是否是课程vj的先决条件。返回一个布尔数组
answer，其中answer[j]是第j个查询的答案。
暴力
- 暴力BFS
class Solution { public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) { // 枚举+BFS List<Integer>[] g = new List[n]; Arrays.setAll(g, e -> new ArrayList<>()); List<Boolean> res = new ArrayList<>(); for (int[] pre : prerequisites){ int u = pre[0], v = pre[1]; g[u].add(v);// v的先决条件是u } for (int[] q : queries){ int u = q[0], v = q[1]; Deque<Integer> queue = new LinkedList<>(); boolean[] vis = new boolean[n]; queue.addLast(u); vis[u] = true; boolean find = false; while(!queue.isEmpty()){ int node = queue.pollFirst(); if (node == v){ find = true; break; } for (int next : g[node]){ if (!vis[next]){ queue.addLast(next); vis[next] = true; } } } res.add(find); } return res; } }
枚举k ，并枚举u 和v ，如果u 是k 的先决条件并且k是v 的先决条件，那么u 是v 的先决条件
实现
class Solution { public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) { List<Boolean> res = new ArrayList<>(); boolean[][] f = new boolean[n][n];// f[i][j]代表i是否是j的先决条件 for (int[] pre : prerequisites){ int u = pre[0], v = pre[1]; f[u][v] = true; } for (int k = 0; k < n; k++){ for (int u = 0; u < n; u++){ for (int v = 0; v < n; v++){ f[u][v] |= f[u][k] && f[k][v]; } } } for (int[] q : queries){ int u = q[0], v = q[1]; res.add(f[u][v]); } return res; } }
class Solution { public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) { // 拓扑排序 List<Integer>[] g = new List[n]; int[] inDeg = new int[n]; Arrays.setAll(g, e -> new ArrayList<>()); List<Boolean> res = new ArrayList<>(); boolean[][] f = new boolean[n][n];// f[i][j]代表i是否是j的先决条件 for (int[] pre : prerequisites){ int u = pre[0], v = pre[1]; g[u].add(v); inDeg[v]++; } Deque<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++){ if (inDeg[i] == 0){ queue.addLast(i); } } while (!queue.isEmpty()){ int u = queue.pollFirst(); for (int v : g[u]){ f[u][v] = true; for (int k = 0; k < n; k++){ f[k][v] |= f[k][u];//k -> u -> v } if(--inDeg[v] == 0){ queue.addLast(v); } } } for (int[] q : queries){ int u = q[0], v = q[1]; res.add(f[u][v]); } return res; } }
