leetcode-210

题目

Course Schedule II

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:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

分析

这道题是典型的图论的算法题，主题就是拓扑排序：把图中的所有节点排序，使得所有的边都从排在前面的节点指向排在后面的节点。

本题给出了节点数量和以节点对来表示的边的数组。

一般来说，要做拓扑排序，有两种解法：

1. 遍历图，找到所有入度为0的节点(源)，然后删去这个节点以及从它出去的边，重复这个过程
2. 使用DFS，记录每个节点的post值，然后按post值递减进行排序

此外，如果图不是DAG，图中有环的话，是没有拓扑排序的，这很容易理解，而上面两种方法也有不同的判断是否有环的方法：

1. 在遍历过程中，如果在剩下的节点集合中找不到源，剩余节点数又大于0，就有环
2. 在DFS过程中，如果有这样的一条边：从已计算出post值的节点指向一个已有prev值、但是没有post值的节点，则有环(即存在回边)

解法一

采用删除源的方法，我们首先要记录所有节点的入度inDegree，然后重复以下过程：

• 找到源，把它加入到结果数组order的尾部
• 删除源，具体操作为：从记录inDegree的map中删除它的记录，然后删除从源出去的边，并把这些边指向的节点的inDegree减一
• 找不到源时，即有环，没有结果

通过使用unordered_map，我们不仅可以快速获取一个节点的入度，而且删除节点也十分高效。

代码

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

//解法一:删除源
//判断有无环:没有源，但节点集合又不为空
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        int num = numCourses;
        unordered_map<int, int> inDegree;
        for (int i = 0; i < numCourses; ++i) inDegree[i] = 0;
        vector<int> order;
        for (int i = 0; i < prerequisites.size(); ++i) {
            inDegree[prerequisites[i].first]++;
        }
        while (num != 0) {
            bool flag = false;
            for (unordered_map<int, int>::iterator itr = inDegree.begin(); itr != inDegree.end();) {
                if (itr->second == 0) {
                    flag = true;
                    order.push_back(itr->first);
                    //删除从源出去的边
                    for (vector<pair<int, int>>::iterator it = prerequisites.begin(); it != prerequisites.end();) {
                        if (it->second == itr->first) {
                            inDegree[it->first]--;
                            it = prerequisites.erase(it);
                        }
                        else it++;
                    }
                    //删除源
                    itr = inDegree.erase(itr);
                    num--;
                }
                else itr++;
            }
            //有环
            if (flag == false) return {};
        }
        return order;
    }
};

解法二

使用DFS来遍历一次图，获取每个节点的post值，然后利用post值的降序来进行排序。

• prev值表示开始访问节点返回的时刻
• post值表示访问完节点返回的时刻

使用DFS来遍历图的伪代码：

func dfs
	for all	v in V do
		visited[v] = false
	for all v in V do
		if not visited[v] : explore(v)

func explore(v) 
	visited[v] = true
	previsit(v)
	for each edge (v, u) in E do
		if not visited[u] : explore(u)
	postvisit(v)

func prevvisit(v)
	prev[v] = clock
	clock++
	
func postvisit(v)
	post[v] = clock
	clock++

要判断是否有环的话，判断是否有回边即可：有边从已有post值的节点指向已有prev值、但没有post值的节点。

通过构建邻接表，我们可以快速获取从节点出发的边所指向的下一节点，实现O(V+E)的时间复杂度的DFS算法。

代码

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

//解法二:通过DFS获取post值，按post值递减排序
//判断有无环:如果有一条边由已有post值的点指向有prev值、但没有post值的点，则有环
class Solution {
private:
    //邻接表
    vector<vector<int> > adjList;
    vector<bool> visited;
    vector<int> prev;
    vector<int> post;
    int clock = 1;
    bool hasCircle = false;
    vector<int> order;
    void explore(int node) {
        visited[node] = true;
        //previsit
        prev[node] = clock;
        clock++;
        for (int i = 0; i < adjList[node].size(); ++i) {
            if (visited[adjList[node][i]] == false) explore(adjList[node][i]);
            else if (post[adjList[node][i]] == 0) hasCircle = true;
        }
        //postvisit
        post[node] = clock;
        clock++;
        order.insert(order.begin(), node);
    }

public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        visited = vector<bool>(numCourses, false);
        prev = vector<int>(numCourses, 0);
        post = vector<int>(numCourses, 0);
        adjList = vector<vector<int>>(numCourses);
        //构建邻接表
        for (int i = 0; i < prerequisites.size(); ++i) 
            adjList[prerequisites[i].second].push_back(prerequisites[i].first);
        
        for (int i = 0; i < numCourses; ++i) {
            if (visited[i] == false) {
                explore(i);
            }
        }

        if (hasCircle == true) return {};
        else return order;
    }

};