There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: 2, [[1,0]] Output:[0,1]Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is[0,1] .
Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output:[0,1,2,3] or [0,2,1,3]Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is[0,1,2,3]. Another correct ordering is[0,2,1,3] .
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
在LeetCode Course Schedule的基础上，要求输出一种拓扑排序结果。
因为已经知道拓扑排序的Kahn解法，即BFS解法，那么输出一种拓扑排序的结果是很简单的事。在BFS的过程中，存储在队列中的点肯定都是入度为0的点，也就是这些课程可以在这一阶段完成，所以我们只需要在每轮BFS的时候，保存一下这一轮的节点就好了。
完整代码如下：
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int> >& prerequisites)
{
vector<unordered_set<int> > pre(numCourses), next(numCourses);
for (const auto& p : prerequisites) {
pre[p.first].insert(p.second);
next[p.second].insert(p.first);
}
vector<int> ans;
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (pre[i].empty())
q.push(i);
}
int edges = prerequisites.size();
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; ++i) {
int cur = q.front();
ans.push_back(cur);
q.pop();
for (const auto& nxt : next[cur]) {
pre[nxt].erase(cur);
–edges;
if (pre[nxt].empty())
q.push(nxt);
}
}
}
if (edges > 0)
return {};
else
return ans;
}
};本代码提交AC，用时23MS。
二刷。在上一题的基础上，要求输出拓扑排序的顺序，比之前简单的解法代码，不需要unordered_set：
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
vector<int> indegree(numCourses, 0);
for (int i = 0; i < prerequisites.size(); ++i) {
int a = prerequisites[i][0], b = prerequisites[i][1];
graph[b][a] = 1;
++indegree[a];
}
vector<int> ans;
while (true) {
int validid = -1;
for (int i = 0; i < numCourses; ++i) {
if (indegree[i] == 0) {
validid = i;
--indegree[i];
break;
}
}
if (validid == -1)break;
ans.push_back(validid);
for (int i = 0; i < numCourses; ++i) {
if (graph[validid][i] == 1) {
graph[validid][i] = 0;
--indegree[i];
}
}
}
if (ans.size() != numCourses)return { };
return ans;
}
};本代码提交AC，用时80MS。
如上图是《算法导论》中关于拓扑排序的一个例子，这是某位教授起床后需要穿戴衣物的顺序，比如只有先穿了袜子才能穿鞋、但是穿鞋和戴手表并没有严格的先后顺序。拓扑排序的功能就是根据图(a)的拓扑图，得到图(b)中节点的先后顺序。
常见的拓扑排序算法有两种：Kahn算法和基于DFS的算法，这两种算法都很好理解，详细的解释请看维基百科
那么怎么判断生产的拓扑序列是否是严格的有序序列呢？基本原则就是就是任意取序列中的两个点，看能不能比较大小，如果能则是严格有序，否则不是。
我起初想到的是对拓扑序列的第一个节点进行深度遍历，遍历之后如果所有的节点都访问了，那么这是一个严格有序的序列，否则不是。后来证明这是不正确的，比如上图从B点开始DFS，遍历完F之后回溯到B点再访问C点，这样即使它不是严格有序的，但DFS还是访问了所有节点。
后来想到了Floyd算法。对拓扑图进行Floyd算法之后，会得到任意两点之间的最短距离。如果拓扑序列中前面的节点都可以到达后面的节点（最短距离不为无穷），则是严格有序的；否则不是。比如上图的一个拓扑序列为BCADEF（不唯一，还可以是BADEFC），但是C到ADEF的最短距离都是无穷，所以这个序列不是严格有序的。
把这些大的问题搞清楚之后就可以写代码了，一些小细节可以看我代码里的注释。
[cpp]
#include<iostream>
//#include<set>
#include<list>
#include<string>
#include<vector>
using namespace std;
int n,m;
const int MAX_N=26;
const int MAX_DIS=10000;
//*******这些都是维基百科关于拓扑排序（DFS版）里的变量含义
int temporary[MAX_N];
int permanent[MAX_N];
int marked[MAX_N];
//*******************************
int path[MAX_N][MAX_N];
//int dfs_visited[MAX_N];
list<int> L;//拓扑排序生产的顺序链
bool isDAG;//DAG=directed acyclic graph，无回路有向图
//每一个测试用例都要初始化路径
void init_path()
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
path[i][j]=0;
}
//每一次拓扑排序都要初始化temporary，permanent，marked
void init_tpm()
{
isDAG=true;
L.clear();
for(int i=0;i<n;i++)
{
temporary[i]=0;
permanent[i]=0;
marked[i]=0;
}
}
//递归访问。具体看维基百科
void visit(int i)
{
if(temporary[i]==1)
{
isDAG=false;
return;
}
else
{
if(marked[i]==0)
{
marked[i]=1;
temporary[i]=1;
for(int j=0;j<n;j++)
{
if(path[i][j]==1)
{
visit(j);
}
}
permanent[i]=1;
temporary[i]=0;
L.push_front(i);
}
}
}
/*
void init_dfs()
{
for(int i=0;i<n;i++)
dfs_visited[i]=0;
}*/
/*
//DFS有缺陷
void DFS(int v)
{
if(dfs_visited[v]==0)
{
dfs_visited[v]=1;
for(int i=0;i<n;i++)
{
if(dfs_visited[i]==0&&path[v][i]==1)
{
DFS(i);
}
}
}
}*/
//使用Floyd算法来判断生产的拓扑排序是否是严格有序的
bool Floyd()
{
int copy_path[MAX_N][MAX_N];
for(int i=0;i<n;i++)//首先复制一份路径图
for(int j=0;j<n;j++)
{
copy_path[i][j]=path[i][j];
if(i!=j&©_path[i][j]==0)//如果原来两点距离为0，说明他们是不直接连通的
copy_path[i][j]=MAX_DIS;//置为无穷
}
//floyd算法
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) if(copy_path[i][j]>copy_path[i][k]+copy_path[k][j])
copy_path[i][j]=copy_path[i][k]+copy_path[k][j];
vector<int> seq;//把原来用链表的拓扑序列转换成数组，方便后面的操作
list<int>::iterator it=L.begin();
while(it!=L.end())
{
seq.push_back(*it);
it++;
}
//如果这个拓扑链是严格有序的话，则前面的元素到后面的元素一定是可达的。
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++) { if(copy_path[seq[i]][seq[j]]>=MAX_DIS)//如果不可达，则不是严格有序的。
return false;
}
}
return true;
}
//拓扑排序DFS版本。返回0：有回路；1：虽然是拓扑排序，但非连通（不是严格有序）；2：是拓扑排序且连通（严格有序）（即任意两个元素都可以比较大小）
int topological_sorting()
{
for(int i=0;i<n;i++)
{
if(marked[i]==0)
{
visit(i);
}
}
if(!isDAG)
return 0;
else
{
/*init_dfs();
DFS(*L.begin());
for(int i=0;i<n;i++) { if(dfs_visited[i]==0) { return 1; } }*/ if(Floyd()) return 2; else return 1; } } int main() { //freopen("input.txt","r",stdin); string tmp; while(cin>>n>>m&&n&&m)
{
init_path();
vector<string> relations(m);
int i;
for(i=0;i<m;i++)//一次性把所有输入都存起来，免得后续麻烦 { cin>>relations[i];
}
int rs=-1;
for(i=0;i<m;i++)//每增加一个关系，都要重新拓扑排序一次
{
init_tpm();//每次都要初始化
tmp=relations[i];
path[tmp[0]-‘A’][tmp[2]-‘A’]=1;
rs=topological_sorting();
if(rs==0)
{
cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
break;//如果是回路的话，后续的输入可以跳过
}
else if(rs==2)//成功
{
cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
list<int>::iterator it=L.begin();
while(it!=L.end())
{
char c=’A’+*it;
cout<<c;
it++;
}
cout<<"."<<endl;
break;//后续输入跳过
}
}
if(i==m&&rs==1)//如果处理完所有输入都没有形成严格有序的拓扑序列
cout<<"Sorted sequence cannot be determined."<<endl;
}
return 0;
}
[/cpp]
我原本以为又是DFS，又是Floyd，算法时空效率会很低，但是提交后AC，用时125MS，内存244K，也不是很差。
代码中的拓扑排序算法使用的是基于DFS的版本，大家也可以改成Kahn算法。
如果觉得自己的代码是对的，但是提交WA的，可以使用这两个测试数据：