| title | date | tags | ||
|---|---|---|---|---|
课程表---LeetCode210(拓扑排序) |
2020-05-17 16:22:17 -0700 |
|
现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1] 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。似曾相识的拓扑排序，感觉好像在算法课上讲过，这里也就当时温习(yuxi)一下了。
这道题有两个思路，一个是dfs，一个是bfs。
dfs想起来要稍微麻烦一些，当处理一个节点时，先要将他标记为正在处理(2)，然后去处理自己的相邻节点，如果发现了环，这里有两种情况：
- 我的相邻节点状态为正在处理(2)，那么存在环
- 我的相邻节点在自己处理时发现了环 这两种情况，直接return false, 当自己和相邻节点都处理过后，把自己标记为完成处理(1)。 ps: 答案的记录是使用一个栈来记录的，最后再一个个弹出来就是正确答案了。
class Solution {
public:
vector<int> edges[10000]; //记录i节点指向的边
int vis[10000]; //记录是否已经被加入栈
stack<int> ansStack;
bool dfs(int cur)
{
vis[cur] = 2; //表示尝试加入
for(int i=0;i<edges[cur].size();i++)
{
if(vis[edges[cur][i]] == 2) {
return false;
}
else if(vis[edges[cur][i]] == 0){
if(!dfs(edges[cur][i])) return false;
}
else{
//nothing
}
}
ansStack.push(cur);
vis[cur] =1;
return true;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> ans;
for(int i=0;i<numCourses;i++) edges[i].clear();
memset(vis,0,sizeof(vis));
int length = prerequisites.size();
for(int i=0;i<length;i++)
{
edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
for(int i=0;i<numCourses;i++)
{
if( vis[i]==0 ) {
if(!dfs(i)) return ans;
}
}
//把stack里的传到ans vector里面
while(!ansStack.empty())
{
ans.push_back(ansStack.top());
ansStack.pop();
}
// for(int i=0;i<numCourses;i++)
// {
// for(int j=0;j<edges[i].size();j++)
// {
// cout<<edges[i][j]<<" ";
// }
// cout<<endl;
// }
return ans;
}
};bfs的解法就简单很多了，一句话，一直找入度为0的点就行了，当处理完一个点，更新相邻节点的入度。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
//bfs实现
vector<int> ans;
//先统计入度
int inD[10000];
vector<int> edges[10000]; //邻接表
for(int i=0;i<numCourses;i++) inD[i]=0;
int length = prerequisites.size();
for(int i=0;i<length;i++)
{
edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
inD[prerequisites[i][0]]++;
}
// //打印一下入度
// for(int i=0;i<numCourses;i++) cout<<i<<"的入度为："<<inD[i]<<endl;
// //打印一下边
// for(int i=0;i<numCourses;i++)
// {
// cout<<i<<"的边为：";
// for(auto e :edges[i])
// cout<<e<<" ";
// cout<<endl;
// }
//一直把入度为0的点推进队列
queue<int> q;
for(int i=0;i<numCourses;i++)
{
if(inD[i] == 0)
q.push(i);
}
while(!q.empty())
{
int cur = q.front();
for(int i=0;i<edges[cur].size();i++)
{
inD[edges[cur][i]]--;
if(inD[edges[cur][i]] ==0 )
{
q.push(edges[cur][i]);
}
}
ans.push_back(cur);
q.pop();
}
//扫一遍，如果还存在入度不为0的，就return false
for(int i=0;i<numCourses;i++)
{
if(inD[i] != 0)
{
ans.clear();
return ans;
}
}
return ans;
}
};