拓朴排序

相关题目：文件的编译顺序
方法：利用邻接链表的深度优先搜索
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <vector>
 4 
 5 int number_of_vertices,
 6 number_of_edges;  // For number of Vertices (V) and number of edges (E)
 7 std::vector<std::vector<int>> graph;
 8 std::vector<bool> visited;
 9 std::vector<int> topological_order;
10 
11 void dfs(int v) {
12     visited[v] = true;
13     for (int u : graph[v]) {
14         if (!visited[u]) {
15             dfs(u);
16         }
17     }
18     topological_order.push_back(v);
19 }
20 
21 void topological_sort() {
22     visited.assign(number_of_vertices, false);
23     topological_order.clear();
24     for (int i = 0; i < number_of_vertices; ++i) {
25         if (!visited[i]) {
26             dfs(i);
27         }
28     }
29     reverse(topological_order.begin(), topological_order.end());
30 }
31 int main() {
32     std::cout
33         << "Enter the number of vertices and the number of directed edges
";
34     std::cin >> number_of_vertices >> number_of_edges;
35     int x = 0, y = 0;
36     graph.resize(number_of_vertices, std::vector<int>());
37     for (int i = 0; i < number_of_edges; ++i) {
38         //输入x,y表示：点x到点y之间有一条路径
39         std::cin >> x >> y;
40         x--, y--;  // to convert 1-indexed to 0-indexed
41         graph[x].push_back(y);
42     }
43     topological_sort();
44     std::cout << "Topological Order : 
";
45     for (int v : topological_order) {
46         std::cout << v + 1
47             << ' ';  // converting zero based indexing back to one based.
48     }
49     std::cout << '
';
50     return 0;
51 }