拓扑排序

【题目】

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, is it possible for you to finish all courses?

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 it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

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

【题解】

     本题等价于有向图是否有环，显然使用拓扑排序的思想即可求解。

    拓扑排序的思想为：

  （1）从有向图中选取一个入度为0的顶点，输出或保存；

  （2）从有向图中删去此顶点以及所有以它为起点的边；

   重复上述步骤，直至图空；若图不空，存在环。

    这里需要解释一下入度的概念。一个顶点的度是指与该顶点相关联的边的条数，对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。

【代码】

bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { int nSize = prerequisites.size(); if (nSize == 0) return true; vector<int> nIndegree(numCourses, 0); vector<vector<int>> Graph(numCourses); queue<int> sources; for (int i = 0; i < nSize; i++) { nIndegree[prerequisites[i].first]++; //求入度 Graph[prerequisites[i].second].push_back(prerequisites[i].first); //边 } for (int i = 0; i < numCourses; i++) { if (nIndegree[i] == 0) sources.push(i); } int nTotal = 0; while (!sources.empty()) { int nTmp = sources.front(); sources.pop(); int nEdges = Graph[nTmp].size(); for (int i = 0; i < nEdges; i++) { nIndegree[Graph[nTmp][i]]--; if (nIndegree[Graph[nTmp][i]] == 0) sources.push(Graph[nTmp][i]); } nTotal++; } if (nTotal == numCourses) return true; else return false; }       LeetCode 210、Course Schedule II与本题的思路是一致的，区别只在于本题不需要保存拓扑排序的序列，而LeetCode 210需要。