一、考察频率以及难度
考察频率：⭐⭐⭐
笔试题难度：⭐⭐⭐
算法难度：⭐⭐⭐
一般是作为笔试倒数2道题出现。
二、学习技巧
理解好拓扑排序的算法过程，熟记拓扑排序的模板。
积累常见的拓扑排序的应用场景。
三、应用场景
在DAG（有向无环图）节点之间有依赖关系，并且需要按照依赖关系进行遍历的，此时可以考虑拓扑排序的算法来进行求解。
四、算法讲解
拓扑排序是在有向图的基础上，对节点进行排序，使得对于每一条有向边u→v，u都在v之间出现。如下图所示：
输出顺序为[a, b, d, e, c]（或者[a, b, e, d, c] ）
解决这个问题最经典的算法就是使用卡恩(kahn)算法。
核心思想如下：首先，先拿出所有入度为0的点排在前面，并在原图中将它们删除；这时有些点的入度减少了，于是再拿出当前所有入度为0的点放在已经排序的序列后面，然后删除；循环这个过程即可。
当然这个过程必须要保证图是无环的。
五、例题与解析
习题1 勇敢者之旅
你是一名勇敢的探险家，准备进入一个神秘的地牢探险。地牢由 numRooms 个房间组成，记为 0 到 numRooms - 1。在进入某些房间之前，你需要先通过其他房间。房间的先后顺序按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要进入房间 ai 则 必须 先进入房间 bi。例如，先修房间对 [0, 1] 表示：想要进入房间 0，你需要先进入房间 1。
请你判断是否可能按照这些规定的顺序通过所有房间进行探险？如果可以，输出 Yes；否则，输出 No。
输入格式
第一行包含一个整数 numRooms (1 <= numRooms <= 10^5)，表示房间的数量。
第二行包含一个整数 m (0 <= m <= 5000)，表示先决条件的数量。
接下来的 m 行，每行包含两个整数 ai 和 bi (0 <= ai, bi < numRooms)，表示进入房间 ai 之前必须先进入房间 bi。
输出格式
如果可以按照规定顺序通过所有房间，输出 "Yes"；否则，输出 "No"。
示例1
输入
2
1
1 0输出
true示例2
输入
2
2
1 0
0 1输出
false提示
1 <= numRooms <= 10^5
0 <= m <= 5000
每个 prerequisites[i] 中的所有房间对互不相同
题目解析
此题的核心其实是判断是否成环。是否成环问题的判断其实是可以使用拓扑排序来解决的，如果使用kafh算法遍历完以后，遍历的节点数量与所有节点的数量相等，那么说明不成环，否则说明成环。
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int numCourses, m;
cin >> numCourses >> m;
vector<pair<int, int>> edges(m);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
edges[i] = {a, b};
}
vector<int> indegree(numCourses, 0);
vector<vector<int>> outdegree(numCourses);
for (const auto& edge : edges) {
int a = edge.first;
int b = edge.second;
indegree[a]++;
outdegree[b].push_back(a);
}
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (indegree[i] == 0) {
q.push(i);
}
}
int cnt = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
cnt++;
for (int nx : outdegree[node]) {
indegree[nx]--;
if (indegree[nx] == 0) {
q.push(nx);
}
}
}
if (cnt == numCourses) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int numCourses = scanner.nextInt();
int m = scanner.nextInt();
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < m; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
edges.add(new int[]{a, b});
}
int[] indegree = new int[numCourses];
List<List<Integer>> outdegree = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++) {
outdegree.add(new ArrayList<>());
}
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
indegree[a]++;
outdegree.get(b).add(a);
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
int cnt = 0;
while (!queue.isEmpty()) {
int node = queue.poll();
cnt++;
for (int nx : outdegree.get(node)) {
indegree[nx]--;
if (indegree[nx] == 0) {
queue.add(nx);
}
}
}
if (cnt == numCourses) {
System.out.println("Yes");
} else {
System.out.println("No");
}
scanner.close();
}
}Python
from collections import deque
numCourses = int(input())
m = int(input())
edges = []
for _ in range(m):
a,b = map(int, input().split())
edges.append((a, b))
indegree = [0] * numCourses
outdegree = [[] for _ in range(numCourses)]
for a, b in edges:
indegree[a] += 1
outdegree[b].append(a)
queue = deque()
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
cnt = 0
while queue:
node = queue.popleft()
cnt += 1
for nx in outdegree[node]:
indegree[nx] -= 1
if indegree[nx] == 0:
queue.append(nx)
if cnt == numCourses:
print("Yes")
else:
print("No")习题2 外星语言
[测评链接](https://niumacode.com/problem/P1131)
你是一名宇航员，刚刚发现了一颗新的外星星球，并接触到了一种使用英语字母的外星语言。这门语言的字母顺序与英语顺序不同。你获得了一份外星词典，其中的单词已经按照这门新语言的字母顺序进行了排序。你需要根据这份词典还原出外星语言中的字母顺序，并按字母递增顺序排列。如果不存在合法字母顺序，返回 -1。如果存在多种可能的合法字母顺序，返回字典序最小的。
输入格式
第一行包含一个整数 n (1 <= n <= 100)，表示词典中单词的数量。
接下来的 n 行，每行包含一个字符串 word (1 <= word.length <= 100)，表示词典中的一个单词。这些单词仅由小写英文字母组成。
输出格式
如果存在合法的字母顺序，按字母递增顺序输出该顺序。
如果不存在合法的字母顺序，返回 "-1"。
示例1
输入
5
wrt
wrf
er
ett
rftt输出
wertf示例2
输入
2
z
x输出
zx
示例3
输入
3
z
x
z输出
-1提示
1 <= n <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成
题目解析
按照给定的words的顺序，构建图，然后进行拓扑排序即可，最后的拓扑序就是答案。如果拓扑排序进行完，依然存在节点的度数不为0，那么此时成环。
需要注意的是，题目要求结果的字典序最小，所以我们拓扑排序的队列需要使用优先队列，保证每次出队列的一定是字典序最小的字符，这样可以保证结果是字典序最小的。
C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
string alienOrder(vector<string>& words) {
unordered_map<char, vector<char>> graph;
unordered_map<char, int> inDegree;
// Initialize the in_degree with all unique characters
for (const auto& word : words) {
for (char c : word) {
inDegree[c] = 0;
}
}
int n = words.size();
for (int i = 0; i < n - 1; ++i) {
string word1 = words[i];
string word2 = words[i + 1];
int mm = min(word1.length(), word2.length());
if (word1.substr(0, mm) == word2.substr(0, mm) && word1.length() > word2.length()) {
return "";
}
for (int j = 0; j < mm; ++j) {
if (word1[j] != word2[j]) {
graph[word1[j]].push_back(word2[j]);
inDegree[word2[j]]++;
break;
}
}
}
priority_queue<char, vector<char>, greater<char>> pq;
for (const auto& pair : inDegree) {
if (pair.second == 0) {
pq.push(pair.first);
}
}
string result;
while (!pq.empty()) {
char node = pq.top();
pq.pop();
result += node;
for (char neighbor : graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
pq.push(neighbor);
}
}
}
for (const auto& pair : inDegree) {
if (pair.second > 0) {
return "";
}
}
return result;
}
int main() {
int n;
cin >> n;
vector<string> words(n);
for (int i = 0; i < n; ++i) {
cin >> words[i];
}
string result = alienOrder(words);
if (result.empty()) {
cout << "-1" << endl;
} else {
cout << result << endl;
}
return 0;
}Java
import java.util.*;
public class Main {
public static String alienOrder(String[] words) {
Map<Character, List<Character>> graph = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
// Initialize the in_degree with all unique characters
for (String word : words) {
for (char c : word.toCharArray()) {
inDegree.put(c, 0);
}
}
int n = words.length;
for (int i = 0; i < n - 1; i++) {
String word1 = words[i];
String word2 = words[i + 1];
int mm = Math.min(word1.length(), word2.length());
if (word1.substring(0, mm).equals(word2.substring(0, mm)) && word1.length() > word2.length()) {
return "";
}
for (int j = 0; j < mm; j++) {
if (word1.charAt(j) != word2.charAt(j)) {
graph.computeIfAbsent(word1.charAt(j), k -> new ArrayList<>()).add(word2.charAt(j));
inDegree.put(word2.charAt(j), inDegree.get(word2.charAt(j)) + 1);
break;
}
}
}
PriorityQueue<Character> pq = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : inDegree.entrySet()) {
if (entry.getValue() == 0) {
pq.add(entry.getKey());
}
}
StringBuilder result = new StringBuilder();
while (!pq.isEmpty()) {
char node = pq.poll();
result.append(node);
if (graph.containsKey(node)) {
for (char neighbor : graph.get(node)) {
inDegree.put(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) == 0) {
pq.add(neighbor);
}
}
}
}
for (int value : inDegree.values()) {
if (value > 0) {
return "";
}
}
return result.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String[] words = new String[n];
for (int i = 0; i < n; i++) {
words[i] = scanner.next();
}
String result = alienOrder(words);
if (result.isEmpty()) {
System.out.println("-1");
} else {
System.out.println(result);
}
scanner.close();
}
}Python
import heapq
from collections import defaultdict, deque
from typing import List
n = int(input())
words = []
for _ in range(n):
words.append(input())
graph = defaultdict(list)
indgre = defaultdict(int)
for word in words:
for c in word:
indgre[c] = 0
n = len(words)
for i in range(n-1):
word1 = words[i]
word2 = words[i+1]
mm = min(len(word1), len(word2))
if word1[:mm] == word2[:mm] and len(word1) > len(word2):
print('')
for j in range(min(len(word1), len(word2))):
if word1[j] != word2[j]:
graph[word1[j]].append(word2[j])
indgre[word2[j]] += 1
break
q = []
for key in indgre:
if indgre[key] == 0:
heapq.heappush(q, key)
res = ''
while q:
node = heapq.heappop(q)
res += node
for neighbor in graph[node]:
indgre[neighbor] -= 1
if indgre[neighbor] == 0:
heapq.heappush(q, neighbor)
if sum(indgre.values()) > 0:
print('')
else:
print(res)习题3 迷宫的环路
[测评链接](https://niumacode.com/problem/P1132)
你是一名探险家，刚刚进入了一座古老的迷宫。迷宫中的每个节点代表一个房间，每个房间至多有一个出口。房间之间的连接用一个数组表示，其中 edges[i] 表示从房间 i 可以到达的下一个房间。如果 edges[i] == -1，则表示房间 i 没有出口。你需要找到迷宫中最长的环路，如果没有任何环路，请返回 -1。
输入格式
第一行包含一个整数 n (2 <= n <= 10^5)，表示房间的数量。
第二行包含 n 个整数 edges[i] (-1 <= edges[i] < n)，表示每个房间的出口。如果房间 i 没有出口，则 edges[i] == -1。
输出格式
输出一个整数，表示迷宫中最长环路的长度。如果没有任何环路，返回 -1。
示例
输入
5
3 3 4 2 3输出
3解释：图中的最长环是：2 -> 4 -> 3 -> 2 。这个环的长度为 3 ，所以返回 3 。
输入
4
2 -1 3 1输出
-1解释：图中没有任何环。
提示
n == edges.length
2 <= n <= 10^5
-1 <= edges[i] < n
edges[i] != i
题目解析
由于题目说明了， 每个点只有一个出度边，所以直接拓扑排序就可以把非环中的点找到。然后再去遍历剩余的节点，找到所有环并且记录大小即可。
CPP
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> edges(n);
for (int i = 0; i < n; ++i) {
cin >> edges[i];
}
queue<int> q;
vector<int> indegree(n, 0);
for (int nx : edges) {
if (nx == -1) continue;
indegree[nx]++;
}
for (int i = 0; i < n; ++i) {
if (indegree[i] == 0) {
q.push(i);
}
}
vector<bool> visited(n, false);
while (!q.empty()) {
int node = q.front();
q.pop();
visited[node] = true;
int nx = edges[node];
if (nx == -1) continue;
indegree[nx]--;
if (indegree[nx] == 0) {
q.push(nx);
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
int cur = 0;
int node = i;
while (!visited[node]) {
visited[node] = true;
cur++;
node = edges[node];
}
ans = max(ans, cur);
}
if (ans != 0) {
cout << ans << endl;
} else {
cout << -1 << endl;
}
return 0;
}Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] edges = new int[n];
for (int i = 0; i < n; i++) {
edges[i] = scanner.nextInt();
}
Queue<Integer> queue = new LinkedList<>();
int[] indegree = new int[n];
for (int nx : edges) {
if (nx != -1) {
indegree[nx]++;
}
}
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.add(i);
}
}
boolean[] visited = new boolean[n];
while (!queue.isEmpty()) {
int node = queue.poll();
visited[node] = true;
int nx = edges[node];
if (nx == -1) continue;
indegree[nx]--;
if (indegree[nx] == 0) {
queue.add(nx);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int cur = 0;
int node = i;
while (!visited[node]) {
visited[node] = true;
cur++;
node = edges[node];
}
ans = Math.max(ans, cur);
}
if (ans != 0) {
System.out.println(ans);
} else {
System.out.println(-1);
}
scanner.close();
}
}Python
from collections import deque
from typing import List
n = int(input())
edges = [int(c) for c in input().split()]
q = deque()
n = len(edges)
indegre = [0] * (n)
for nx in edges:
if nx == -1: continue
indegre[nx] += 1
for i in range(n):
if indegre[i] == 0:
q.append(i)
vst = [False] * n
while q:
node = q.popleft()
vst[node] = True
nx = edges[node]
if nx == -1: continue
indegre[nx] -= 1
if indegre[nx] == 0:
q.append(nx)
ans = 0
for i in range(n):
if vst[i]: continue
cur = 0
node = i
while not vst[node]:
vst[node] = True
cur += 1
node = edges[node]
ans = max(ans, cur)
if ans != 0:
print(ans)
else:
print(-1)六、常见陷阱
对于比较绕的背景容易分析不出来拓扑排序的应用,特别是题目没有明显解释有依赖关系的.