??拓撲排序是圖論中一種典型的算法。通過拓撲排序可以梳理圖的層次結構。像什么工期完成類的圖論任務，就是典型的應用。第二個應用就是判斷圖中是否存在環路的問題。
??程序中建圖的方式是鄰接表形式，代碼如下：

vector<vector<int> > graph(n, vector<int>{});

??下面是拓撲排序的模板：

vector<vector<int> > graph(n, vector<int>{});根據所給有向圖的指向關系，完成graph圖的建立// 統計初始入度為0的vector<int> indegree(n, 0);for (int i=0; i<n; i++) {for (int j=0; j<graph[i].size(); j++) {indegree[graph[i][j]]++;}} queue<int> que; // 隊列存儲，其實如果對于順序沒有要求棧也行for (int i=0; i<n; i++) {if (indegree[i] == 0)que.push(i);} while (!que.empty()) {int a = que.front();cout << a + 1 << " ";que.pop();for (int i=0; i<graph[a].size(); i++) {indegree[graph[a][i]]--;if (indegree[graph[a][i]] == 0)que.push(graph[a][i]);}} /*如果要判斷是否存在環路，可以在最后判斷一下indegree數組，如果全為0說明無環，否則說明有環。 */

??來兩道題練習一下吧！（題目是他人博客找的，不是網站來的。沒有去OJ驗證AC，只是通過了樣例測試。輸出格式也沒調，勉強過關吧！）

題目一：確定比賽名次

代碼如下：

#include<bits/stdc++.h> using namespace std;int main(void) {int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>{});for (int i=0; i<m; i++) {int u, v;cin >> u >> v;graph[u-1].push_back(v-1);}vector<int> indegree(n, 0);for (int i=0; i<graph.size(); i++) {for (int j=0; j<graph[i].size(); j++) {indegree[graph[i][j]]++;}}priority_queue<int> que; // 題目對順序有要求，這里用了優先隊列for (int i=0; i<n; i++) {if (indegree[i] == 0)que.push(-i);}while (!que.empty()) {int num = -que.top();cout << num + 1 << " ";que.pop();for (int i=0; i<graph[num].size(); i++) {indegree[graph[num][i]]--;if (indegree[graph[num][i]] == 0)que.push(-graph[num][i]);}}return 0; }

題目二：POJ 2367：Genealogical tree

#include<bits/stdc++.h> using namespace std;int main(void) {int n;cin >> n;vector<vector<int> > graph(n, vector<int>{});int i;for (int j=0; j<n; j++) {while (1) {cin >> i;if (i != 0) graph[j].push_back(i-1);elsebreak;}}vector<int> indegree(n, 0);for (int i=0; i<n; i++) {for (int j=0; j<graph[i].size(); j++) {indegree[graph[i][j]]++;}} queue<int> que;for (int i=0; i<n; i++) {if (indegree[i] == 0)que.push(i);} while (!que.empty()) {int a = que.front();cout << a + 1 << " ";que.pop();for (int i=0; i<graph[a].size(); i++) {indegree[graph[a][i]]--;if (indegree[graph[a][i]] == 0)que.push(graph[a][i]);}}return 0; }

參考資料：https://blog.csdn.net/wang_123_zy/article/details/81411683

總結

以上是生活随笔為你收集整理的经典拓扑排序模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。