拓扑排序：每个节点的前置节点都在这个节点之前。
要求：有向图、没有环
拓扑排序的顺序可能不只一种。拓扑排序也可以用来判断有没有环
1.在图中找到所有入度为0的点。
2.把所有入度为0的点在图中删掉，重点是删掉影响！继续找到入度为0的点并删掉影响。
3.直到所有点都被删掉，依次删除的顺序就是正确的拓扑排序结果。
4.如果无法把所有的点都删掉，说明有向图里有环。
下面我们看一些可以直接使用拓扑排序解决的题目。
题目一
测试链接：https://leetcode.cn/problems/course-schedule-ii
分析：对于这道题，就是一个拓扑排序的模板。代码如下。
class Solution {
public:int Head[2005] = {0};int Next[10000] = {0};int To[10000] = {0};int cnt = 1;int indegree[2005] = {0};void build(vector<vector<int>>& prerequisites){int length = prerequisites.size();for(int i = 0;i < length;++i){Next[cnt] = Head[prerequisites[i][1]+1];Head[prerequisites[i][1]+1] = cnt;To[cnt] = prerequisites[i][0]+1;++cnt;++indegree[prerequisites[i][0]];}}vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> ans;int len1 = 0;int len2 = 0;int temp;build(prerequisites);for(int i = 0;i < numCourses;++i){if(indegree[i] == 0){ans.push_back(i);++len2;}}while (len2 != len1){temp = len1;len1 = len2;for(int i = temp;i < len1;++i){for(int j = Head[ans[i]+1];j != 0;j = Next[j]){if(--indegree[To[j]-1] == 0){ans.push_back(To[j]-1);++len2;}}}}if(len1 != numCourses){ans.clear();}return ans;}
};其中，采用的是链式前向星建图；并未使用队列将答案暂时存储，而是直接遍历存储答案的数组实现入度的更新。
题目二
测试链接：https://www.luogu.com.cn/problem/U107394
分析：对于需要字典序最小的拓扑排序，可以使用优先队列，也就是堆暂时存储答案。代码如下。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int Head[100002] = {0};
int Next[100002] = {0};
int To[100002] = {0};
int indegree[100002] = {0};
int ans[100002];
int cnt = 1;
int main(void){int n, m, u, v, index = 0;priority_queue<int, vector<int>, greater<int>> q;scanf("%d%d", &n, &m);for(int i = 0;i < m;++i){scanf("%d%d", &u, &v);Next[cnt] = Head[u];Head[u] = cnt;To[cnt] = v;++cnt;++indegree[v];}for(int i = 1;i <= n;++i){if(indegree[i] == 0){indegree[i] = -1;q.push(i);}}while (!q.empty()){ans[index++] = q.top();q.pop();for(int i = Head[ans[index-1]];i != 0;i = Next[i]){if(--indegree[To[i]] == 0){q.push(To[i]);}}}for(int i = 0;i < n;++i){printf("%d ", ans[i]);}
}其中，采用链式前向星建图；使用优先队列暂时存储答案实现入度的更新并且使得最终答案的字典序最小。
题目三
测试链接：https://leetcode.cn/problems/Jf1JuT/
分析：对于这个题比较容易想到的是，如果a字典序小于b则a指向b，但是还需要一些细节处理。比如需要统计哪些小写字母出现了，需要一个exist数组；同时，对于字符串的比较需要分为几种情况；并且因为可能存在多次同一个指向，所以我们需要统计有效边的数目，用于最终判断拓扑排序是否完成；对于不可能出现的情况，直接返回空字符串。代码如下。
class Solution {
public:int graph[26][26] = {0};int indegree[26] = {0};bool exist[26] = {false};int numOfb;bool build(vector<string>& words){int length = words.size();for(int i = 0;i < length;++i){int len1 = words[i].size();for(int a = 0;a < len1;++a){exist[words[i][a] - 'a'] = true;}for(int j = i+1;j < length;++j){int len2 = words[j].size();int index = 0;while (index < len1 && index < len2 && words[i][index] == words[j][index]){++index;}if(index < len1 && index == len2){return true;}if(index < len1){if(graph[words[i][index] - 'a'][words[j][index] - 'a'] == 0){graph[words[i][index] - 'a'][words[j][index] - 'a'] = 1;++indegree[words[j][index] - 'a'];++numOfb;}}}}return false;}string alienOrder(vector<string>& words) {string ans;numOfb = 0;int len1 = 0, len2 = 0, temp;char ch;if(build(words)){return ans;}for(int i = 0;i < 26;++i){if(indegree[i] == 0 && exist[i] == true){indegree[i] = -1;ch = 'a' + i;ans += ch;++len2;}}while (len2 != len1){temp = len1;len1 = len2;for(int i = temp;i < len1;++i){for(int j = 0;j < 26;++j){if(graph[ans[i] - 'a'][j] == 1){--numOfb;if(--indegree[j] == 0){++len2;ch = 'a' + j;ans += ch;}}}}}if(numOfb != 0){ans.clear();}return ans;}
};其中，使用邻接矩阵建图；numOfb是有效边的数目；build方法初始化变量，返回值代表是否有不可能情况出现，出现返回true；直接在答案数组中遍历实现更新入度；最后通过有效边是否为0判断拓扑排序是否成功。
题目四
测试链接：https://leetcode.cn/problems/stamping-the-sequence
分析：对于这个题，可以考虑在下标i盖章，结果和最终目标有几个不一样，不一样的下标作为节点指向下标i代表的节点，遍历字符串建图成功。则入度为0的节点代表是最后盖下的，然后看一下这个下标盖章可以对相邻的下标盖章时修正多少个错误，也就是更新相邻下标代表节点的入度，这样进行拓扑排序。得到的答案数组逆序即是答案。代码如下。
class Solution {
public:vector<int> movesToStamp(string stamp, string target) {vector<int> ans;vector<int> indegree;int length_s = stamp.size();int length_t = target.size();indegree.assign(length_t - length_s + 1, length_s);vector<vector<int>> graph;vector<int> temp;for(int i = 0;i < length_t;++i){graph.push_back(temp);}vector<int> q;q.assign(length_t - length_s + 1, 0);int l = 0, r = 0;for(int i = 0;i <= length_t - length_s;++i){for(int j = 0;j < length_s;++j){if(target[i+j] == stamp[j]){if(--indegree[i] == 0){q[r++] = i;}}else{graph[i+j].push_back(i);}}}vector<bool> visited;visited.assign(length_t, false);int size = 0;while (l < r){int cur = q[l++];ans.push_back(cur);++size;for(int i = 0;i < length_s;++i){if(!visited[cur+i]){visited[cur+i] = true;for(int next = 0;next < graph[cur+i].size();++next){if(--indegree[graph[cur+i][next]] == 0){q[r++] = graph[cur+i][next];}}}}}if(size != length_t - length_s + 1){ans.clear();return ans;}for(int i = 0, j = size-1;i < j;++i, --j){ans[i] = ans[i] ^ ans[j];ans[j] = ans[i] ^ ans[j];ans[i] = ans[i] ^ ans[j];}return ans;}
};其中，采用邻接表建图。
除了以上的题目，还可以利用拓扑排序的过程，上游节点逐渐推送消息给下游节点。下面我们通过一些题目加深理解。
题目五
测试链接：https://www.luogu.com.cn/problem/P4017
分析：这个利用拓扑排序可以传递一些信息，从最开始入度为0的节点代表走到这些节点，有一条食物链。这些节点指向的下一节点，将这些节点的食物链数统计相加，直到传到最终节点，更新答案。代码如下。
#include <iostream>
using namespace std;
#define MOD 80112002
int n;
int m;
int Head[5002] = {0};
int Next[500002] = {0};
int To[500002] = {0};
int cnt = 1;
int indegree[5002] = {0};
int numsOfget[5002] = {0};
int q[5002] = {0};
int main(void){int A, B;int ans = 0;scanf("%d%d", &n, &m);for(int i = 0;i < m;++i){scanf("%d%d", &A, &B);Next[cnt] = Head[A];Head[A] = cnt;To[cnt] = B;++indegree[B];++cnt;}int l = 0, r = 0;for(int i = 1;i <= n;++i){if(indegree[i] == 0){numsOfget[i] = 1;q[r++] = i;}}while (l < r){int cur = q[l++];for(int next = Head[cur];next != 0;next = Next[next]){numsOfget[To[next]] = (numsOfget[To[next]] + numsOfget[cur]) % MOD;if(--indegree[To[next]] == 0){q[r++] = To[next];}}if(Head[cur] == 0){ans = (ans + numsOfget[cur]) % MOD;}}printf("%d", ans);
}其中，采用链式前向星建图；取余部分采用了加法同余原理。
题目六
测试链接：https://leetcode.cn/problems/loud-and-rich/
分析：这个题可以考虑，如果i比j更有钱，则i指向j。同时初始化答案数组下标和值相等，然后开始拓扑排序。节点入度为0时代表答案确定。同时，对于入度为0的节点的指向节点，更新指向节点的答案，也就是传递信息。将指向节点的答案值和传递过来的答案值进行比较，更新答案。拓扑排序完成即可得到答案。代码如下。
class Solution {
public:int Head[501] = {0};int Next[124750] = {0};int To[124750] = {0};int cnt = 1;int q[501] = {0};int indegree[501] = {0};void build(vector<vector<int>>& richer){int length = richer.size();for(int i = 0;i < length;++i){Next[cnt] = Head[richer[i][0]+1];Head[richer[i][0]+1] = cnt;To[cnt] = richer[i][1]+1;++indegree[richer[i][1]];++cnt;}}vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {build(richer);int n = quiet.size();vector<int> ans;for(int i = 0;i < n;++i){ans.push_back(i);}int l = 0, r = 0;for(int i = 0;i < n;++i){if(indegree[i] == 0){q[r++] = i;}}while (l < r){int cur = q[l++];for(int next = Head[cur+1];next != 0;next = Next[next]){ans[To[next]-1] = quiet[ans[To[next]-1]] < quiet[ans[cur]] ? ans[To[next]-1] : ans[cur];if(--indegree[To[next]-1] == 0){q[r++] = To[next]-1;}}}return ans;}
};其中，采用链式前向星建图；主题和拓扑排序一样，只在while循环中有更新答案的代码。
题目七
测试链接：https://leetcode.cn/problems/parallel-courses-iii/
分析：这个题和前面的食物链的题很像，可以求出所有食物链中所需时间最长的数这个就是答案。即还是通过拓扑排序传递的信息，就是前面的节点向后面的节点传递了最大时间。代码如下。
class Solution {
public:int Head[50002] = {0};int Next[50002] = {0};int To[50002] = {0};int cnt = 1;int indegree[50002] = {0};int cost[50002] = {0};int q[50002] = {0};int build(vector<vector<int>>& relations, vector<int>& time, int n){int length = relations.size();for(int i = 0;i < length;++i){Next[cnt] = Head[relations[i][0]];Head[relations[i][0]] = cnt;To[cnt] = relations[i][1];++cnt;++indegree[relations[i][1]];}int index = 0;for(int i = 1;i <= n;++i){cost[i] = time[i-1];if(indegree[i] == 0){q[index++] = i;}}return index;}int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {int r = build(relations, time, n);int ans = 0;int l = 0;while (l < r){int cur = q[l++];for(int next = Head[cur];next != 0;next = Next[next]){cost[To[next]] = cost[To[next]] > cost[cur] + time[To[next]-1] ? cost[To[next]] : cost[cur] + time[To[next]-1];if(--indegree[To[next]] == 0){q[r++] = To[next];}}if(Head[cur] == 0){ans = ans > cost[cur] ? ans : cost[cur];}}return ans;}
};其中，采用链式前向星建图；主体代码和前面食物链的题一样，只是传递的信息不一样。
题目八
测试链接：https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/
分析：这个题可以考虑大环和小环，小环代表两个人互为喜欢，然后两个人各有一个喜欢链，即很多人链式喜欢，最后到这两个人。对于这个小环的最大人数就是这两个人形成的喜欢链的人数之和，而这张圆形的桌子可以存在多个小环。大环就是喜欢的人成环时人数大于2。这时只能算成环的人数，而不能加上喜欢链，并且桌子上只能存在一个大环。所以最终答案是所有小环人数之和和最大大环人数相比，取最大值。代码如下。
class Solution {
public:int nums[100002];int indegree[100002] = {0};int q[100002] = {0};bool visited[100002] = {false};int maximumInvitations(vector<int>& favorite) {int n = favorite.size();int l = 0, r = 0;int small = 0, big = 0;for(int i = 0;i < n;++i){++indegree[favorite[i]];nums[i] = 1;}for(int i = 0;i < n;++i){if(indegree[i] == 0){q[r++] = i;visited[i] = true;}}while (l < r){int cur = q[l++];int love = favorite[cur];nums[love] = nums[love] > 1+nums[cur] ? nums[love] : 1+nums[cur];if(--indegree[love] == 0){q[r++] = love;visited[love] = true;}}for(int i = 0;i < n;++i){if(indegree[i] != 0 && visited[i] == false){if(i == favorite[favorite[i]]){small += (nums[i] + nums[favorite[i]]);visited[i] = true;visited[favorite[i]] = true;}else{int temp = favorite[i];int num = 1;visited[temp] = true;while (i != temp){temp = favorite[temp];visited[temp] = true;++num;}big = big > num ? big : num;}}}return small > big ? small : big;}
};其中，采用链式前向星建图；先通过拓扑排序将环搞出来，然后依次判断环的类型以及更新答案；visited数组代表节点是否被访问。
