卡码网KamaCoder 105. 有向图的完全可达性

本文主要是介绍卡码网KamaCoder 105. 有向图的完全可达性，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：105. 有向图的完全可达性

C++题解1：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main(){int N, K;cin>>N>>K;// 如果边的数量不够，则一定不能到达所有点if(N-2 >= K) {cout<<-1; return 0;}// path存放路径，visited标记是否能到达vector<vector<int>> path(K, vector<int>(2, 0));for(int i = 0; i < K; i++){cin>>path[i][0]>>path[i][1];}vector<bool> visited(N, false);visited[0] = true;// 二维数组sort排序第一个，这样路径就是从小往大排的。// 比如遍历完1能到达的地方，下一个是看2能不能到达，而不会看3，把2跳过sort(path.begin(), path.end());for(int i = 0; i < K; i++) {// 只有第一个值能到达，路径的第二个才能到达if(visited[ path[i][0] - 1 ]) visited[path[i][1]-1] = true;}// 判断是否有没有到达的地方if(find(visited.begin(), visited.end(), false) == visited.end()) cout<<1;else cout<<-1;return 0;
}

C++题解2：深度优先。使用list<int>存储。来源代码随想录

// 写法一：dfs 处理当前访问的节点
#include <iostream>
#include <vector>
#include <list>
using namespace std;void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {if (visited[key]) {return;}visited[key] = true;list<int> keys = graph[key];for (int key : keys) {// 深度优先搜索遍历dfs(graph, key, visited);}
}int main() {int n, m, s, t;cin >> n >> m;// 节点编号从1到n，所以申请 n+1 这么大的数组vector<list<int>> graph(n + 1); // 邻接表while (m--) {cin >> s >> t;// 使用邻接表 ，表示 s -> t 是相连的graph[s].push_back(t);}vector<bool> visited(n + 1, false);dfs(graph, 1, visited);//检查是否都访问到了for (int i = 1; i <= n; i++) {if (visited[i] == false) {cout << -1 << endl;return 0;}}cout << 1 << endl;
}

C++题解3：广度优先。来源代码随想录

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;int main() {int n, m, s, t;cin >> n >> m;vector<list<int>> graph(n + 1);while (m--) {cin >> s >> t;graph[s].push_back(t);}vector<bool> visited(n + 1, false);visited[1] = true; //  1 号房间开始queue<int> que;que.push(1); //  1 号房间开始// 广度优先搜索的过程while (!que.empty()) {int key = que.front(); que.pop();list<int> keys = graph[key];for (int key : keys) {if (!visited[key]) {que.push(key);visited[key] = true;}}}for (int i = 1; i <= n; i++) {if (visited[i] == false) {cout << -1 << endl;return 0;}}cout << 1 << endl;
}

这篇关于卡码网KamaCoder 105. 有向图的完全可达性的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---