Leetcode刷题 | Day63_图论08_拓扑排序

 一、学习任务

• 拓扑排序代码随想录

二、具体题目

1.拓扑排序117. 软件构建

【题目描述】

某个大型软件项目的构建系统拥有 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;
}