华为23实习笔试2_拓扑排序
2022/4/7 23:21:23
本文主要是介绍华为23实习笔试2_拓扑排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
输入一个有向图,判断能否到达目标节点
不能到达输出-1,可以输出路径
//#include<bits/stdc++.h> #include<cstring> #include <algorithm> #include <iostream> #include <vector> #include <stack> using namespace std; int relay[5000][5000]; //依赖关系 bool arr[5000];//记录是否能到达 bool att[5000];//记录访问过,防止循环依赖,访问过但不可达直接返回false stack<int> s; //记录路径 bool dfs(int n) { s.push(n); if(relay[n][0]==0){ return true; } if(arr[n]){ //可达 return true; }else if(att[n]){ //排除循环依赖 return false; } att[n] = true; //访问过 bool b = true; for (int i = 1; i <= relay[n][0];i++) { b = b & dfs(relay[n][i]); } if(b){ arr[n] = true;//可达 return true; }else{ s.pop(); } return false; } int main() { int n,m; cin >> n>>m; memset(relay, 0, sizeof(relay)); memset(arr, 0, sizeof(arr)); memset(att, 0, sizeof(att)); string str; for (int i = 0; i < n;i++){ cin >> str; int tmp = 0,count=0;//分割整数,整数数组中的列数 for(auto ch:str){ if(ch!=','){ tmp = tmp * 10 + ch - '0'; }else{ relay[i][count] = tmp; tmp = 0; count++; } } relay[i][count] = tmp; tmp = 0; count++; } bool b = dfs(m); if(b){ cout << s.top(); s.pop(); while(s.size()>1){ int t = s.top(); s.pop(); cout <<","<< t ; } }else{ cout << -1 << endl; } return 0; } /* 输入: 4 2 0 1,0 1,1 2,0,1 输出: 0,1 解释: 执行0后可以执行1,之后可以执行任务2; 输出 0,1后可以执行目标任务 拓扑排序 节点个数,目标任务编号; 节点依赖个数:依赖节点编号 */
这篇关于华为23实习笔试2_拓扑排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解
- 2024-04-07以一当十丨TiDB 在东吴证券秀财 APP 的应用实践
- 2024-04-07月活超 1.1 亿,用户超 4 亿,你也在用的「知乎」是如何在超大规模 TiDB 集群上玩转多云多活的?来听听知乎代晓磊的答案!