LeetCode 1462. Course Schedule IV

DFS

We can use DFS to solve this problem. We should memo the results to make sure that we will no have the TLE.

A reference code can be found here.

class Solution {
public:
set<int> dfs(vector<bool>& visited, vector<vector<int>>& graph, vector<set<int>>& s, int i)
{
if (visited[i])
{
return s[i];
}
else
{
set<int> ret;
for (auto j : graph[i])
{
ret.insert(j);
auto this_s = dfs(visited, graph, s, j);
for (auto x : this_s)
{
ret.insert(x);
}
}
s[i] = ret;
visited[i] = true;
return s[i];
}
}
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries)
{
vector<vector<int>> graph(n);
vector<set<int>> s(n);
for (auto p : prerequisites)
{
graph[p[1]].push_back(p[0]);
}
vector<bool> visited(n, false);
for (int i = 0; i < n; ++i)
{
dfs(visited, graph, s, i);
}
vector<bool> ret;
for (auto q : queries)
{
ret.push_back(s[q[1]].count(q[0]));
}
return ret;
}
};

We can also use Floyd Warshall to solve this problem[2].

int dp[100+10][100+10];
class Solution {
public:
vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries)
{
memset(dp, 0, sizeof(dp));
for (auto p : prerequisites)
{
dp[p[0]][p[1]] = 1;
}
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
dp[i][j] = dp[i][j] || (dp[i][k] && dp[k][j]);
vector<bool> ret;
for (auto q : queries)
ret.push_back(dp[q[0]][q[1]]);
return ret;
}
};

Reference

[1]https://youtu.be/mXncR8of7Ns

[2]https://leetcode.com/problems/course-schedule-iv/discuss/660509/JavaPython-FloydWarshall-Algorithm-Clean-code-O(n3)

Data Scientist/MLE/SWE @takemobi