题1：
指路：117. 软件构建 (kamacoder.com)
思路与代码：
文件的依赖关系，有些文件不止依赖于一个文件同样有些文件也不止被一个文件依赖。拓补排序，经典的图论问题。拓补序列，意在将依赖关系转为线性序列，值得注意的是，拓补序列中也不允许有环形关系的存在，因此可作为判断是否存在环形关系的条件。那么，拓补序列指的是所有能将有向无环图线性排序的算法，具体算法有：BFS和DFS。在这里，我们先了解BFS，那么它有两个要点，一为将度为0的节点加入结果集，一为将节点从图中移除。循环要点直到图中无节点。来看一下本题，题目说给出n个文件，共m对文件依赖关系，m对关系中前者为s，后者为t，也就是说s文件决定t文件，t文件依赖于s文件。那么根据刚刚的要点，我们需要一个不依赖于任何文件的首文件充当线性排序的首节点。于是乎，我们就在这里定义一个vector容器用以盛放文件的入度信息，同时定义一个unordered_map表用以记录文件的依赖关系，当文件的入度数组对应值为0时证明没有该文件不依赖任何文件，那么定义一个队列让其入队充当首节点。之后执行第二步将节点从图中删除，标记当前节点，在map中找到该文件指向的文件，入度减一，循环操作。最后如果无环则输出，否则输出-1。代码如下：
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;int main() {int m, n, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 记录每个文件的入度unordered_map<int, vector<int>> umap; // 文件依赖关系vector<int> result; // 结果while (m--) {// s -> tcin >> s >> t;inDegree[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.size()) {int cur = que.front(); // 当前选中的文件que.pop();result.push_back(cur);vector<int> files = umap[cur]; // 获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]]--; // cur文件入度-1if (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] ;}else cout << -1 << endl;
}