Formatted question description: https://leetcode.ca/all/1462.html

1462. Course Schedule IV (Medium)

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have direct prerequisites, for example, to take course 0 you have first to take course 1, which is expressed as a pair: [1,0]

Given the total number of courses n, a list of direct prerequisite pairs and a list of queries pairs.

You should answer for each queries[i] whether the course queries[i][0] is a prerequisite of the course queries[i][1] or not.

Return a list of boolean, the answers to the given queries.

Please note that if course a is a prerequisite of course b and course b is a prerequisite of course c, then, course a is a prerequisite of course c.

 

Example 1:

Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: course 0 is not a prerequisite of course 1 but the opposite is true.

Example 2:

Input: n = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites and each course is independent.

Example 3:

Input: n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

Example 4:

Input: n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
Output: [false,true]

Example 5:

Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]

 

Constraints:

• 2 <= n <= 100
• 0 <= prerequisite.length <= (n * (n - 1) / 2)
• 0 <= prerequisite[i][0], prerequisite[i][1] < n
• prerequisite[i][0] != prerequisite[i][1]
• The prerequisites graph has no cycles.
• The prerequisites graph has no repeated edges.
• 1 <= queries.length <= 10^4
• queries[i][0] != queries[i][1]

Related Topics:
Graph

Solution 1. DFS

We can first build a directed graph given the prerequisite. Then for each query, we DFS to check we can reach q[1] from q[0]. To save computation, we can memoize the result of any from, to node pairs we’ve seen along the DFS process.

// OJ: https://leetcode.com/problems/course-schedule-iv/

// Time: O(V + E)
// Space: O(V^2)
class Solution {
    vector<vector<int>> G, m;
    bool dfs(int from, int to) {
        if (m[from][to] != -1) return m[from][to];
        bool ans = false;
        for (int v : G[from]) {
            if (dfs(v, to)) {
                ans = true;
                break;
            }
        }
        return m[from][to] = ans;
    }
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& A, vector<vector<int>>& Q) {
        G.assign(n, {});
        m.assign(n, vector<int>(n, -1));
        for (int i = 0; i < n; ++i) m[i][i] = 1;
        for (auto &e : A) G[e[0]].push_back(e[1]);
        vector<bool> ans;
        for (auto &e : Q) ans.push_back(dfs(e[0], e[1]));
        return ans;
    }
};

Solution 2. Floyd-Warshall

We can use the Floyd-Warshall algorithm to fine all the shortest paths of any node pairs in a weighted graph. Here we can make simple adjustment to it to just store whether any node pairs are reachable.

// OJ: https://leetcode.com/problems/course-schedule-iv/

// Time: O(V^3)
// Space: O(V^2)
class Solution {
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& A, vector<vector<int>>& Q) {
        vector<vector<bool>> m(n, vector<bool>(n));
        for (auto &e : A) m[e[0]][e[1]] = true;
        for (int i = 0; i < n; ++i) {
            for (int u = 0; u < n; ++u) {
                for (int v = 0; v < n; ++v) {
                    m[u][v] = m[u][v] || (m[u][i] && m[i][v]);
                }
            }
        }
        vector<bool> ans;
        for (auto &q : Q) ans.push_back(m[q[0]][q[1]]);
        return ans;
    }
};

Java

class Solution {
    public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
        Map<Integer, Set<Integer>> prerequisiteMap = new HashMap<Integer, Set<Integer>>();
        for (int[] prerequisite : prerequisites) {
            int course0 = prerequisite[0], course1 = prerequisite[1];
            Set<Integer> set = prerequisiteMap.getOrDefault(course0, new HashSet<Integer>());
            set.add(course1);
            prerequisiteMap.put(course0, set);
        }
        List<Boolean> checkList = new ArrayList<Boolean>();
        Map<Integer, Boolean> queryMap = new HashMap<Integer, Boolean>();
        int queriesCount = queries.length;
        for (int i = 0; i < queriesCount; i++) {
            int[] query = queries[i];
            boolean isPrerequisite = search(prerequisiteMap, queryMap, query[0], query[1], n);
            checkList.add(isPrerequisite);
        }
        return checkList;
    }

    public boolean search(Map<Integer, Set<Integer>> prerequisiteMap, Map<Integer, Boolean> queryMap, int course0, int course1, int n) {
        int key = course0 * n + course1;
        if (queryMap.containsKey(key))
            return queryMap.get(key);
        Set<Integer> set = prerequisiteMap.getOrDefault(course0, new HashSet<Integer>());
        if (set.contains(course1)) {
            queryMap.put(key, true);
            return true;
        } else {
            for (int nextCourse : set) {
                if (search(prerequisiteMap, queryMap, nextCourse, course1, n)) {
                    queryMap.put(key, true);
                    return true;
                }
            }
        }
        queryMap.put(key, false);
        return false;
    }
}

All Problems

All Solutions