leetcode 1462. Course Schedule IV 课程表 IV

Problem: 1462. Course Schedule IV 课程表 IV

状态表 + 深度优先搜索，若从起点出发找到了target目标就提前结束搜索，用flag来标记

Code

class Solution { public: vector<int> router; vector<bool> ret, status; unordered_map<int, unordered_set<int>> ump; unordered_set<int> launch; bool flag = false; int target; void dfs(vector<vector<int>>& tr, int start) { if(flag) return; status[start] = true; for(int& next : tr[start]) { if(status[next]==false) { if(next == target) { flag = true; return; } dfs(tr, next); } } } vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) { vector<vector<int>> tr(numCourses); int n = prerequisites.size(), m = queries.size(), cc, ce; ret.assign(m, false); for(vector<int>& pqt : prerequisites) { tr[pqt[0]].push_back(pqt[1]); } for(vector<int>& pqt : queries) launch.insert(pqt[0]); for(int i = 0; i < m; i++) { cc = queries[i][0]; ce = queries[i][1]; target = ce; flag = false; status.assign(numCourses, false); dfs(tr, cc); ret[i] = flag; } return ret; } };

额，可以使用矩阵来表示两者之间的前置关系

class Solution { public: vector<vector<bool>> pre; vector<bool> ret, status; int m, n; void dfs(vector<vector<int>>& tr, int start) { if(status[start]) return; status[start] = true; for(int& next : tr[start]) { // if(status[next]==false) { pre[start][next] = true; dfs(tr, next); for(int i = 0; i < pre.size(); i++) { pre[start][i] = pre[start][i] | pre[next][i]; } // } } } vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) { vector<vector<int>> tr(numCourses); n = prerequisites.size(), m = queries.size(); int cc, ce; ret.assign(m, false); for(vector<int>& pqt : prerequisites) { tr[pqt[0]].push_back(pqt[1]); } status.assign(numCourses, false); pre.assign(numCourses, vector<bool>(numCourses, false)); for(int i = 0; i < m; i++) { cc = queries[i][0]; ce = queries[i][1]; dfs(tr, cc); ret[i] = pre[cc][ce]; } return ret; } };