我已经为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;
}
};
实际上，您的函数是正确的，但效率很低。
这是因为在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。。。。。
所以，像这样，你将重新计算相同的子问题。为了避免这种情况，您需要放置另一个数组，只需检查节点是否已经计算完毕。
因此，我引入了另一个向量var(初始化为false(，如果节点访问并且被批准为非循环节点(不涉及循环(，则该向量基本上设置为true。
改进代码：
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。但这仍然是低效的，因为您的逻辑需要按值传递向量。我建议你换一种方式思考：(
我还认为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;
}
}
参考文献
- 有关更多详细信息，请参阅讨论板，您可以在其中找到大量解释良好的公认解决方案，使用各种语言，包括高效算法和渐近时间/空间复杂性分析1，2