#494. 01 邻接矩阵 DFS:从 1 可达的最大编号
题目描述
给定一张包含 个顶点和 条有向边的图,顶点编号为 。
现在从 顶点 出发,只能沿着有向边所指的方向移动。请你求出:从顶点 出发能够到达的顶点中,编号最大的顶点是多少?
规定顶点 本身也属于可达顶点,因此答案一定存在。
本题用于练习 邻接矩阵存图与 DFS(深度优先搜索)。注意:输入的边 表示可以从 到 ,不代表可以从 到 。
输入格式
第一行包含两个整数 ,表示顶点数和有向边数。
接下来 行,每行两个整数 ,表示一条从 指向 的有向边。
输出格式
输出一个整数,表示从顶点 出发能够到达的最大顶点编号。
样例
4 3
1 2
2 4
4 3
4
样例解释
从顶点 出发可以依次到达 、、,加上起点 ,可达顶点集合为 ,因此最大编号为 。
数据范围与说明
- ;
- ;
- ;
- 输入可能包含重边和自环;
- 图是 有向图,不保证连通。
训练目标: 建立 g[u][v] 邻接矩阵,使用 vis 数组防止重复访问,通过 DFS 遍历从 可达的所有点。
手速前三短评
本题当前前三名可评论暂无短评