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

2024-08-21 07:52

本文主要是介绍卡码网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. 有向图的完全可达性的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092563

相关文章

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

uva674(完全背包)

题意: 有5种硬币1,5,10,25,50,;现在随意的给出一个价钱,问你有几种组合方式! 输入11 输出4 1+...+1(10个),5+(6*1),5+5+1,  10+1(共4种) 思路; 满足完全背包思想,状态转移方程:dp[i+num[k]] += dp[i](dp[i]为组合成i的不重复种数,num[k]分别为1,5,10,25,50)不能合在一起转移,否则会导致重复!

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一:卡码网 103. 水流问题 题目链接 题解:DFS 题目二:卡码网 104. 建造最大岛屿 题目链接 题解:DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节,还是选择使用 DFS 来解决这类搜索问题(单纯因为我更熟悉 DFS 一点),今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚

222.完全二叉树的节点个数

(写给未来遗忘的自己) 题目: 代码: class Solution {public:int countNodes(TreeNode* root) {queue<TreeNode*>node_que;if(root==nullptr) return 0;node_que.push(root);int result;while(!node_que.empty()){int layer_s

不完全微分PID控制算法

不完全微分PID控制算法 注:本文内容摘自《先进PID控制MATLAB仿真(第4版)》刘金琨 编著,研读此书受益匪浅,感谢作者! 在PID控制中,微分信号的引入可改善系统的动态特性,但也容易引起高频干扰,在误差扰动突变时尤其显出微分项的不足。若在控制算法中加入低通滤波器,则可以使系统性能得到改善。 克服上述缺点的方法之一是在PID算法中加入一个一阶惯性环节(低通滤波器) G f

代码随想录第八天|151.翻转字符串里的单词 卡码网:55.右旋转字符串 28. 实现 strStr() 459.重复的子字符串

反转字符串的单词 思路:刷过稍微忘记 class Solution {public://去除空格string remove(string s){//使用快慢指针int slow=0;int i=0;for(;i<s.size();i++){if(s[i]!=' '){if(slow!=0){s[slow++]=' ';}while(s[i]!=' '&&i<s.size()){s[slow+

【HDU】3861 The King’s Problem 强连通缩点+有向图最小路径覆盖

传送门:【HDU】3861 The King’s Problem 题目分析:首先强连通缩点,因为形成一个环的王国肯定在一条路径中,这样才能保证拆的少。 然后缩点后就是DAG图了,由于题目要求的是最小路径覆盖,那么二分匹配即可。 代码如下: #include <cstdio>#include <cstring>#include <algorithm>#includ