1462: Course-Schedule-IV
Medium

table of contents

(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.

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