210. 课程表II(拓扑排序)

题目：总共有n门课需要选，一些课程存在先修课程，比如要想学习课程0，需要先修课程1。返回为了学完所有课程所安排的学习顺序，如果有多种正确的顺序，返回一种即可；否则返回空数组。
解析：拓扑排序的典型应用。

1. DFS

逆向思维，最先被放入栈中的节点是拓扑排序中最后面的节点。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> edges;  //存储有向图
vector<int> visited;  //标记每个节点的状态：0=未搜索, 1=搜索中, 2=已完成
vector<int> result;  //用数组模拟栈, 0为栈底, n-1为栈顶
bool valid = true;  //判断有向图中是否有环

void dfs(int u){
    visited[u]=1;  //搜索中
    for(int v: edges[u]){
        if(visited[v] == 0){
            dfs(v);
            if(!valid) return;
        }else if(visited[v] == 1){  //搜索中 说明找到了环
            valid = false;
            return;
        }
    }
    visited[u]=2;  //已完成
    result.push_back(u);  //将该节点入栈
}

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){
    edges.resize(numCourses);
    visited.resize(numCourses);
    for(int i=0; i<prerequisites.size(); i++){
        edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
    }
    //每次挑选一个<未搜索>的节点，开始进行深度优先搜索
    for(int i=0; i<numCourses; i++){
        if(visited[i]==0){
            dfs(i);
        }
        if(!valid) return {};
    }
    reverse(result.begin(), result.end());  //下标0为栈底,因此需要反序输出
    return result;
}

2. BFS

正向思维，按照入度为0的节点顺序生成拓扑排序。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<vector<int>> edges;  //存储有向图
vector<int> indeg;  //存储每个节点的入度 
vector<int> result; 

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){
    edges.resize(numCourses);
    indeg.resize(numCourses);
    for(int i=0; i<prerequisites.size(); i++){
        edges[prerequisites[i][1]].push_back(prerequisites[i][0]);
        indeg[prerequisites[i][0]]++;
    }
    queue<int> q;
    //将所有入度为0的节点放入队列
    for(int i=0; i<numCourses; i++){
        if(indeg[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        result.push_back(u);
        for(int v: edges[u]){
            indeg[v]--;
            if(indeg[v]==0){
                q.push(v);
            }
        }
    }

    if(result.size() != numCourses) return {};
    return result;
}