Я получаю сообщение об ошибке TLE при выполнении определения цикла - PullRequest
Новая
       105

Я получаю сообщение об ошибке TLE при выполнении определения цикла

0 голосов
/ 04 августа 2020

Я написал код для проблемы 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;
    }
};

Ответы [ 2 ]

2 голосов
/ 04 августа 2020

На самом деле ваша функция правильная, но такая неэффективная.

Это потому, что в 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)

Итак, для этого графика для начальной вершины 0 (с вашим кодом ) для функции bool:

итерация - 1: вы выполняете DFS и проверяете 1 и 2 и ..... .

итерация - 2: вы выполняете DFS и проверяете 3 и снова 2 .....

Итак таким образом вы будете пересчитывать те же подзадачи. Чтобы избежать этого, вам нужно поместить другой массив, просто проверьте, вычислен ли уже узел.

Итак, я ввел еще один вектор var (инициализированный как false), который в основном устанавливается в true, если node равен посещено и утверждено как нецикловый узел (который не входит в цикл).

Улучшено Код: 

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, не меняя основы c logi c . Но это все еще неэффективно, так как ваш logi c должен передавать вектор по значению. Предлагаю вам подумать иначе :)

2 голосов
/ 04 августа 2020

Я также думаю, что 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;
  }
}

Ссылки

...