LeetCode 1462. Course Schedule IV

DFS

1462. Course Schedule IV

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)