解析
2024-09-14 19:43:48
发布于:浙江
4阅读
0回复
0点赞
题目大意
给出个顶点条边的无向图(不一定是连通图),要求你从1~n号顶点出发,求能够前往的最大编号的顶点编号是多少 打印出来
思路分析
-
深度优先搜索/广度优先搜索
-
邻接表/邻接矩阵的使用
-
存储地图
-
邻接矩阵存储/邻接表存储地图
-
int mp[1005][1005] ; // 邻接矩阵存储地图 int n,m; cin >> n >> m; while(m--) // 存储地图 { int u,v; cin >> u >> v; // 输入m条边得起点和终点 mp[u][v] = 1; // 把这条边得关系保存在邻接矩阵当中 }
-
-
以任意一个顶点作为起点,然后通过深/广搜前往能够去得所有顶点
-
行走得过程当中,记录下经过得最大顶点编号
-
// 写法1 int answer ; bool vis[1005]; void dfs(int it){ // it 代表当前所处的顶点编号 // 使用深搜查询经过的顶点取最大的 vis[it] = true; answer = max(answer,it) ; // 暴力枚举最大的顶点 for(int i = 1 ; i <= n ; i ++ ) { // 枚举其他可以到达得顶点 if(mp[it][i] && !vis[i]){ dfs(i); // 没有来过并且有边那就去 } } } for(int i = 1 ; i <= n ; i ++ ){ answer = 0 ; for(int j = 1 ; j <= n ; j ++ ) vis[j] = false; // 清空数据 dfs(i); // 以任意顶点作为出发得顶点 cout << answer << endl; }
-
这里空空如也
有帮助,赞一个