#494. 01 邻接矩阵 DFS:从 1 可达的最大编号

题目描述

给定一张包含 NN 个顶点和 MM 条有向边的图,顶点编号为 1,2,…,N1,2,\ldots,N。

现在从 顶点 11 出发,只能沿着有向边所指的方向移动。请你求出:从顶点 11 出发能够到达的顶点中,编号最大的顶点是多少?

规定顶点 11 本身也属于可达顶点,因此答案一定存在。

本题用于练习 邻接矩阵存图与 DFS(深度优先搜索)。注意:输入的边 (u,v)(u,v) 表示可以从 uu 到 vv,不代表可以从 vv 到 uu。

输入格式

第一行包含两个整数 N,MN,M,表示顶点数和有向边数。

接下来 MM 行,每行两个整数 u,vu,v,表示一条从 uu 指向 vv 的有向边。

输出格式

输出一个整数,表示从顶点 11 出发能够到达的最大顶点编号。

样例

4 3
1 2
2 4
4 3
4

样例解释

从顶点 11 出发可以依次到达 22、44、33,加上起点 11,可达顶点集合为 {1,2,3,4}\{1,2,3,4\},因此最大编号为 44。

数据范围与说明

  • 1≤N≤10001\le N\le 1000;
  • 1≤M≤10001\le M\le 1000;
  • 1≤u,v≤N1\le u,v\le N;
  • 输入可能包含重边和自环;
  • 图是 有向图,不保证连通。

训练目标: 建立 g[u][v] 邻接矩阵,使用 vis 数组防止重复访问,通过 DFS 遍历从 11 可达的所有点。

手速前三短评

本题当前前三名可评论

暂无短评