华为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-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?