我在执行循环检测时收到 TLE 错误

Question

我已经为 leetcode 问题 (courseSchedule) 编写了一个代码，它基本上询问是否可以在给定依赖项的情况下完成一组给定的课程。我的方法是创建一个图形，然后检查一个循环，但是，它给出了一个 TLE 错误。你能帮我解释一下为什么会发生 TLE 或者我是否可以使用更好的方法？

bool cycle( vector<vector<int>> &adj,int i,vector<bool> vis){
    
    if(vis[i])
        return true;
    
    vis[i]=true;
    
    for(int k=0;k<adj[i].size();k++)
       if(cycle(adj,adj[i][k],vis))
           return true;
    
    return false;
}

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<vector<int>> adj(numCourses);
        
        for(int i=0;i<prerequisites.size();i++)
            adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        vector<bool> vis(numCourses,false);
        
        for(int i=0;i<numCourses;i++)
            if(cycle(adj,i,vis))
                return false;
        
        return true;
    }
};

Answer 1

我也认为 vis 没有通过引用传递将是大型测试用例的问题。

这是一个类似深度优先搜索图的方法，会通过：

#include <cstdint>
#include <utility>
#include <vector>

const static struct Solution {
    static bool canFinish(
        const int num_courses,
        const std::vector<std::vector<int>>& prerequisites
    ) {
        GraphType graph = buildCourseGraph(prerequisites, num_courses);
        std::vector<bool> to_take(num_courses, false);
        std::vector<bool> taken(num_courses, false);

        for (SizeType course = 0; course < num_courses; ++course) {
            if (!taken[course] && !validateAcyclic(graph, course, to_take, taken)) {
                return false;
            }
        }

        return true;
    }

private:
    using GraphType = std::vector<std::vector<int>>;
    using SizeType = std::uint_fast16_t;
    static GraphType buildCourseGraph(
        const std::vector<std::vector<int>>& prerequisites,
        const SizeType num_courses
    ) {
        GraphType graph(num_courses);

        for (const auto& prerequisite : prerequisites) {
            graph[prerequisite[1]].emplace_back(prerequisite[0]);
        }

        return graph;
    }

    static bool validateAcyclic(
        const GraphType& graph,
        const SizeType& course,
        std::vector<bool>& to_take,
        std::vector<bool>& taken
        
    ) {
        if (to_take[course]) {
            return false;
        }

        if (taken[course]) {
            return true;
        }

        to_take[course] = taken[course] = true;

        for (const auto& adj_course : graph[course]) {
            if (!validateAcyclic(graph, adj_course, to_take, taken)) {
                return false;
            }
        }

        to_take[course] = false;
        return true;
    }
};

这里是 LeetCode 在 Java 中的深度优先搜索解决方案（带注释）：

class Solution {
  public boolean canFinish(int numCourses, int[][] prerequisites) {

    // course -> list of next courses
    HashMap<Integer, List<Integer>> courseDict = new HashMap<>();

    // build the graph first
    for (int[] relation : prerequisites) {
      // relation[0] depends on relation[1]
      if (courseDict.containsKey(relation[1])) {
        courseDict.get(relation[1]).add(relation[0]);
      } else {
        List<Integer> nextCourses = new LinkedList<>();
        nextCourses.add(relation[0]);
        courseDict.put(relation[1], nextCourses);
      }
    }

    boolean[] checked = new boolean[numCourses];
    boolean[] path = new boolean[numCourses];

    for (int currCourse = 0; currCourse < numCourses; ++currCourse) {
      if (this.isCyclic(currCourse, courseDict, checked, path))
        return false;
    }

    return true;
  }


  /*
   * postorder DFS check that no cycle would be formed starting from currCourse
   */
  protected boolean isCyclic(
      Integer currCourse, HashMap<Integer, List<Integer>> courseDict,
      boolean[] checked, boolean[] path) {

    // bottom cases
    if (checked[currCourse])
      // this node has been checked, no cycle would be formed with this node.
      return false;
    if (path[currCourse])
      // come across a previously visited node, i.e. detect the cycle
      return true;

    // no following courses, no loop.
    if (!courseDict.containsKey(currCourse))
      return false;

    // before backtracking, mark the node in the path
    path[currCourse] = true;

    boolean ret = false;
    // postorder DFS, to visit all its children first.
    for (Integer child : courseDict.get(currCourse)) {
      ret = this.isCyclic(child, courseDict, checked, path);
      if (ret)
        break;
    }

    // after the visits of children, we come back to process the node itself
    // remove the node from the path
    path[currCourse] = false;

    // Now that we've visited the nodes in the downstream,
    // we complete the check of this node.
    checked[currCourse] = true;
    return ret;
  }
}

参考资料

有关更多详细信息，请参阅 Discussion Board which you can find plenty of well-explained accepted solutions in there, with a variety of languages including efficient algorithms and asymptotic time/space complexity analysis^{1, 2}。

Answer 2

实际上，你的函数是正确的，但效率太低了。

这是因为在 cycle 函数中执行了太多冗余操作，即多次检查同一节点。

您的代码：

bool cycle( vector<vector<int>> &adj,int i,vector<bool> vis){
    
    if(vis[i])
        return true;
    
    vis[i] = true;
    
    for(int k = 0; k < adj[i].size(); k++)
       
       if(cycle(adj, adj[i][k], vis))
           return true;
    
    return false;
}

例如：

0 ---> 1 ---> 2 ......... (some more edges)

0 ---> 3 ---> 2 ---> 4 ........ (some more edges)

因此，对于此图，对于 bool 函数的起始顶点 0（使用您的代码）：

迭代 - 1: 您执行 DFS 并检查 1 和 2 以及 ......

迭代 - 2: 你执行 DFS 并检查 3 并再次检查 2 .. ...

因此，像这样，您将重新计算相同的 sub-problems。为避免这种情况，您需要放置另一个数组来检查是否已经计算了一个节点。

所以我引入了另一个向量 var（初始化为 false），如果节点 visited，它基本上设置为 true并且被批准为non-cycle节点（不涉及循环）。

改进代码：

bool cycle( vector<vector<int>> &adj,int i,vector<bool> vis, vector<bool>& var){
    
    // if i involves in cycle and visited in the current sequence
    if(!var[i] and vis[i])
        return true;
    
    vis[i] = true;
    
    for(int k=0;k<adj[i].size();k++) {
       
       // if adj[i][k] is true i.e doesn't involve in cycle, so no need to check it. If it is false we should check it.
       if(!var[adj[i][k]] and cycle(adj,adj[i][k],vis, var))
           return true;
       else 
        var[adj[i][k]] = true; // else setting true to tell it doesn't involve in cycle
    }

    // setting true to tell it doesn't involve in cycle
    var[i] = true;
    
    return false;
}


class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<vector<int>> adj(numCourses);
        
        for(int i=0;i<prerequisites.size();i++)
            adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        vector<bool> vis(numCourses,false);
        vector<bool> var(numCourses,false);
        
        for(int i=0;i<numCourses;i++)
            if(cycle(adj,i,vis, var))
                return false;
        
        return true;
    }
};

注：

我只是做了一些小改动，让你的代码在不改变基本逻辑的情况下克服 TLE。但这仍然效率低下，因为您的逻辑需要按值传递向量。我建议你换个思路:)

我在执行循环检测时收到 TLE 错误

I am getting a TLE error while performing cycle detection

c++

graph

depth-first-search

参考资料