【題目描述】

某個大型軟件項目的構建系統擁有 N 個文件，文件編號從 0 到 N - 1，在這些文件中，某些文件依賴于其他文件的內容，這意味著如果文件 A 依賴于文件 B，則必須在處理文件 A 之前處理文件 B （0 <= A, B <= N - 1）。請編寫一個算法，用于確定文件處理的順序。

【輸入描述】

第一行輸入兩個正整數 N, M。表示 N 個文件之間擁有 M 條依賴關系。

后續 M 行，每行兩個正整數 S 和 T，表示 T 文件依賴于 S 文件。

【輸出描述】

輸出共一行，如果能處理成功，則輸出文件順序，用空格隔開。

如果不能成功處理（相互依賴），則輸出 -1。

拓撲排序：BFS/DFS

本篇方法為BFS

拓撲排序的過程，只有兩步：

1. 找到入度為0 的節點，加入結果集
2. 將該節點從圖中移除

循環以上兩步，直到 所有節點都在圖中被移除了。

結果集的順序，就是我們想要的拓撲排序順序 （結果集里順序可能不唯一）

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;int main() {int n, m, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 記錄每個文件的入度unordered_map<int, vector<int>> umap; // 記錄文件依賴關系vector<int> result; // 記錄處理文件順序while (m--) {// s->t，先有s再有tcin >> s >> t;inDegree[t]++; // t入度+1umap[s].push_back(t); // 把s指向的文件放入對應的數組}queue<int> que;for (int i = 0; i < n; i++) {// 入度為0的文件，可以作為開頭，先加入隊列if (inDegree[i] == 0) que.push(i);}while (!que.empty()) {int cur = que.front(); // 當前入度為0的第一個文件que.pop(); // 彈出處理過的result.push_back(cur); // 處理過的放入結果集vector<int> files = umap[cur]; // 獲取該文件所指向的所有文件if (!files.empty()) { // 如果該節點有指向的文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]]--; // 刪除節點 = 把cur指向的所有文件入度減一if (inDegree[files[i]] == 0) que.push(files[i]);}}}if (result.size() == n) {for (int i = 0; i < n - 1; i ++) {cout << result[i] << " ";}cout << result[n - 1] << endl;}else {cout << -1 << endl;}return 0;
}