A7374 | 午枫的城市路线
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
在一座城市中，有 $N$ 个路口，编号为 $1 \sim N$。
城市中共有 $M$ 条单向道路，每条道路 $(a_i, b_i)$ 表示可以从路口 $a_i$ 直接前往路口 $b_i$。
这些道路构成了一张有向图。现在，小午从路口 $1$ 出发，他想知道：是否存在一条路径，能够从路口 $1$ 出发，沿着道路前进，最终又回到路口 $1$？这样的路径称为一个回环路线（即起点和终点相同的路径）。
如果存在这样的回环路线，请你输出所有包含路口 $1$ 的回环中，边数最少的那一条的长度；
如果不存在这样的回环，则输出 $-1$。
城市中共有 $M$ 条单向道路，每条道路 $(a_i, b_i)$ 表示可以从路口 $a_i$ 直接前往路口 $b_i$。
这些道路构成了一张有向图。现在，小午从路口 $1$ 出发，他想知道：是否存在一条路径，能够从路口 $1$ 出发，沿着道路前进，最终又回到路口 $1$？这样的路径称为一个回环路线（即起点和终点相同的路径）。
如果存在这样的回环路线，请你输出所有包含路口 $1$ 的回环中，边数最少的那一条的长度；
如果不存在这样的回环，则输出 $-1$。
输入格式
第一行输入两个整数 $N, M$，表示路口数量和道路数量；
接下来 $M$ 行，每行两个整数 $a_i, b_i$，表示一条从路口 $a_i$ 指向路口 $b_i$ 的单向道路。
接下来 $M$ 行，每行两个整数 $a_i, b_i$，表示一条从路口 $a_i$ 指向路口 $b_i$ 的单向道路。
输出格式
如果存在包含路口 $1$ 的回环，输出其最少边数；否则输出 $-1$。
输入输出样例
输入 #1
3 3 1 2 2 3 3 1
输出 #1
3
解释说明
在示例一中，存在一条回环路线：$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$
这条路径从路口 $1$ 出发并回到 $1$，长度为 $3$，因此答案为 $3$。
在示例二中，从路口 $1$ 出发无法回到自身，因此不存在回环路线，答案为 $-1$。
数据范围
对于 $100\%$ 的测试数据，满足：$2 \le N \le 2 \times 10^5$，$1 \le M \le \min\left(\frac{N(N-1)}{2},\ 2 \times 10^5\right)$，$1 \le a_i, b_i \le N$，$a_i \neq b_i$，不存在重边或反向重复边。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？