代码随想录算法训练营第五十八天 | 图论part08
117. 软件构建
在这一题中，只需要输出一种方法。使用BFS的方法，找到入度为0的节点，将其从树中删去，重复上述步骤，直到没有入度为0的节点。如果此时没有删除所有的节点，表明这个有向图有环，输出-1.否则，正常输出。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <fstream>using namespace std;int main() {int n, m;int s, t;ifstream infile("input.txt");cin >> n >> m;unordered_map<int, vector<int>> table;vector<int> inDegrees(n, 0);while (m--) {cin >> s >> t;inDegrees[t]++;table[s].emplace_back(t);}queue<int> que;for (int i = 0; i < n; ++i) {if (inDegrees[i] == 0)que.push(i);}vector<int> result;while (!que.empty()) {int cur = que.front();que.pop();result.push_back(cur);for (int t : table[cur]) {inDegrees[t]--;if (inDegrees[t] == 0)que.push(t);}}if (result.size() != n) cout << -1;else {for (int i = 0; i < n - 1; ++i) cout << result[i] << " ";cout << result[n - 1];}return 0;
}
47. 参加科学大会
思路是三部：
- 找到距离源点最近的节点
- 将节点标记为已访问
- 更新非访问节点的minDist
本算法所需要的数据结构：
存放图的临接矩阵
记录访问的一维数组
记录到源点的距离的一维数组
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <fstream>
#include <climits>
using namespace std;int main() {int n, m;int s, e, v;ifstream infile("input.txt");cin >> n >> m;vector<vector<int>> graph(n + 1, vector<int>(n + 1, INT_MAX));while (m--) {cin >> s >> e >> v;graph[s][e] = v;}// 记录访问的一维数组vector<bool> visited(n + 1, false);// 记录到源点的距离的一维数组 vector<int> minDist(n + 1, INT_MAX);minDist[1] = 0;for (int i = 1; i <= n; ++i) {// 找到距离源点最近的节点int cur = 1;int minVal = INT_MAX;for (int v = 1; v <= n; ++v) {if (!visited[v] && minDist[v] < minVal) {cur = v;minVal = minDist[v];}}// 将节点标记为已访问visited[cur] = true;// 更新非访问节点的minDistfor (int e = 1; e <= n; ++e) {if (!visited[e] && graph[cur][e] != INT_MAX && graph[cur][e] + minVal < minDist[e])minDist[e] = graph[cur][e] + minVal;}}if (minDist[n] == INT_MAX) cout << -1 << endl;else cout << minDist[n] << endl;return 0;
}