LeetCode#210 Course Schedule II（C++版）

题干：

There are a total of n courses you have to take, labeled from 

 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.

For example:

2, [[1,0]]      

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]

4, [[1,0],[2,0],[3,1],[3,2]]      

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]

.

题意解读：

该题比较好理解，就是拓扑排序，若输出的结点数小于顶点数，则图有环输出空字符串，反之输出一个拓扑序，一下是广度优先遍历的c++实现版

class Solution {
public:
    vector<int> findOrder(int numCourse, vector<pair<int, int> >& prerequisite) {
    	numCourses = numCourse; 
    	prerequisites = prerequisite;
    	//计算入度的函数 
    	find_In_degree();
    	//拓扑排序的函数 
    	find_topo_sort();
    	if(topo_sort.size() == numCourses)
    	return topo_sort;
    	else return {};
    }
    void find_In_degree() {
    	for(int i = 0; i < numCourses; i++) {
    		in_degree.push_back(0);
		}
    	vector<pair<int,int> >::iterator it;
    	for(it = prerequisites.begin(); it != prerequisites.end(); it++) {
    		in_degree[it->first]++;
		}
	}
	void find_topo_sort() {
		int zeros = -1;
		for(int i = 0; i < numCourses; i++) {
			zeros = -1;
			//寻找入度为0的点 
			for(int j = 0; j < numCourses; j++) {
				if(in_degree[j] == 0) {
					zeros = j;
					break;
				}
			}
			//找到入度为0的点后，把所有与该结点相连的边 删掉 
			if(zeros != -1) {
			topo_sort.push_back(zeros);
			in_degree[zeros] = -1;
			vector<pair<int,int> >::iterator it;
			for(it = prerequisites.begin(); it != prerequisites.end(); it++) {
    			if(it->second == zeros) {
    				in_degree[it->first]--;
    			}
			}
			}
		}
	}
private:
	int numCourses;
	vector<pair<int, int> > prerequisites;
	vector<int> in_degree;
    vector<int> topo_sort;
};