Course Schedule IV

(I really wanted to make a bitset solution work)

My solution to this questions involves depth-first search.

First, I wanted to record all the edges in an adjacency matrix so that I can run DFS on every node. For every node, I want to be able to store the prerequisites of every node in a bitset (with 0 being not prerequisites and vice versa). To do this, I defined a vector<bitset<101>> (since the problem statement defines there to be a maximum of 100 different nodes).

Then, we run DFS on every node and use the 101th bit to help determine if we have seen this node or not (0 being unseen, and 1 being seen), since we only need 100 bits for 100 different nodes.

• if we have seen the node before, we can simply or the bitset of the node with its parent node (so the parent node will share the same prerequisites)
• if we have not seen the node before, we just run DFS on the children of the node, and eventually or the bitset of the children node with the parent's bitset

Then, after running DFS on every node, for every query, we should be able to index into the vector<bitset<101>> to be able to return if query[0] is a prerequisite of query[1].

code

class Solution {
public:
    constexpr static auto init = bitset<101> (1) << 100;
    bitset<101>& dfs (int index, vector<vector<int>> &adjacencyMatrix, vector<bitset<101>> &isPrerequisite) {
        auto& ans = isPrerequisite[index];
        if (ans != init) {
            return ans;
        }
        ans.reset();
        for (auto &node : adjacencyMatrix[index]) {
            ans.set(node);
            ans |= dfs(node, adjacencyMatrix, isPrerequisite);
        }
        return ans;
    }
    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        vector<vector<int>> adjacencyMatrix (numCourses);
        vector<bitset<101>> isPrerequisite (numCourses, init);

        for (auto &edges : prerequisites) {
            adjacencyMatrix[edges[0]].push_back(edges[1]);
        }

        for (int i = 0; i < numCourses; ++i) {
            dfs(i, adjacencyMatrix, isPrerequisite);
        }

        vector<bool> ans;
        for (auto &query : queries) {
            ans.push_back(isPrerequisite[query[0]][query[1]]);
        }
        return ans;
    }
};

complexity

• Time: O(n^2) (where n is the number of nodes)
• Space: O(n^2)