43

Code 1

class Solution {
public:
  std::vector<bool>
  checkIfPrerequisite(int n, std::vector<std::vector<int>> &prerequisites,
                      std::vector<std::vector<int>> &queries) {
    // construct graph matrix
    std::vector<std::vector<bool>> graph_matrix(n, std::vector<bool>(n, false));
    for (int i = 0; i < prerequisites.size(); ++i) {
      graph_matrix[prerequisites[i][0]][prerequisites[i][1]] = true;
    }
    std::vector<bool> rtn;
    for (int i = 0; i < queries.size(); ++i) {
      std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
      bool res = dfs(queries[i][0], queries[i][1], visited, graph_matrix);
      rtn.push_back(res);
    }
    return rtn;
  }

  bool dfs(int src, int dst, std::vector<std::vector<bool>> &visited,
           const std::vector<std::vector<bool>> &graph_matrix) {
    if (graph_matrix[src][dst]) {
      return true;
    }
    for (int i = 0; i < visited.size(); ++i) {
      if (graph_matrix[src][i] && !visited[src][i]) {
        visited[src][i] = true;
        if (dfs(i, dst, visited, graph_matrix))
          return true;
        visited[src][i] = false;
      }
    }
    return false;
  }
};

Result1

Time Limit Exceeded

Code2

class Solution {
public:
  std::vector<bool>
  checkIfPrerequisite(int n, std::vector<std::vector<int>> &prerequisites,
                      std::vector<std::vector<int>> &queries) {
    // construct graph matrix
    std::vector<std::vector<bool>> graph_matrix(n, std::vector<bool>(n, false));
    for (int i = 0; i < prerequisites.size(); ++i)
      graph_matrix[prerequisites[i][0]][prerequisites[i][1]] = true;
    for (int i = 0; i < graph_matrix.size(); ++i)
      graph_matrix[i][i] = true;
    for (int k = 0; k < n; ++k) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          if (graph_matrix[i][j])
            continue;
          else
            graph_matrix[i][j] = graph_matrix[i][k] && graph_matrix[k][j];
        }
      }
    }
    std::vector<bool> rtn;
    for (int i = 0; i < queries.size(); ++i) {
      rtn.push_back(graph_matrix[queries[i][0]][queries[i][1]]);
    }
    return rtn;
  }
};

Result2

Success

Runtime: 340 ms, faster than 65.18% of C++ online submissions for Course Schedule IV.

Memory Usage: 59.2 MB, less than 93.81% of C++ online submissions for Course Schedule IV.