A6507 | 道路修建
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
在某座城市里，有 $n$ 个交通枢纽，编号为 $1$ 到 $n$。
这些枢纽之间可以修建双向道路。如果枢纽 $x$ 和枢纽 $y$ 之间有一条道路，那么车辆可以从 $x$ 直接开到 $y$，也可以从 $y$ 直接开到 $x$。
目前，城市中已经建成了 $m$ 条道路，第 $i$ 条道路连接枢纽 $u_i$ 和枢纽 $v_i$。
现在，城市交通部门希望增加更多的道路，但必须按照以下规则来修建：
- 规则：选择三个不同的枢纽 $x, y, z$，满足：
- $x$ 和 $y$ 之间已经有一条道路；
- $y$ 和 $z$ 之间已经有一条道路；
- 但 $x$ 和 $z$ 之间没有直接道路。
那么就可以在 $x$ 和 $z$ 之间修建一条新的双向道路。
注意：新建的道路之后也可以被用于后续的修建规则中。
按照上述规则，最多能修建多少条新道路？
这些枢纽之间可以修建双向道路。如果枢纽 $x$ 和枢纽 $y$ 之间有一条道路，那么车辆可以从 $x$ 直接开到 $y$，也可以从 $y$ 直接开到 $x$。
目前，城市中已经建成了 $m$ 条道路，第 $i$ 条道路连接枢纽 $u_i$ 和枢纽 $v_i$。
现在，城市交通部门希望增加更多的道路，但必须按照以下规则来修建：
- 规则：选择三个不同的枢纽 $x, y, z$，满足：
- $x$ 和 $y$ 之间已经有一条道路；
- $y$ 和 $z$ 之间已经有一条道路；
- 但 $x$ 和 $z$ 之间没有直接道路。
那么就可以在 $x$ 和 $z$ 之间修建一条新的双向道路。
注意：新建的道路之后也可以被用于后续的修建规则中。
按照上述规则，最多能修建多少条新道路？
输入格式
第一行输入两个正整数 $n,m$ $(2\leq n \leq 2\times10^5,0\leq m \leq 2\times 10^5)$ ，分别表示交通枢纽的数量以及双向道路的数量。
接下来 $m$ 行，每行两个整数 $u_i,v_i$ $(1\leq u_i < v_i \leq n)$ ，表示第 $i$ 条道路连接的两个交通枢纽。
接下来 $m$ 行，每行两个整数 $u_i,v_i$ $(1\leq u_i < v_i \leq n)$ ，表示第 $i$ 条道路连接的两个交通枢纽。
输出格式
输出一个整数表示最多可以修建的新道路数量。
输入输出样例
输入 #1
4 3 1 2 2 3 1 4
输出 #1
3
样例 1 解释
按照规则，最多可以新建 3 条道路：
1 与 2 有道路，2 与 3 有道路，但 1 与 3 没有直接道路 → 新建道路 1–3
1 与 3 有道路（上一步新建），3 与 4 有道路，但 1 与 4 没有直接道路 → 新建道路 1–4
2 与 1 有道路，1 与 4 有道路（上一步新建），但 2 与 4 没有直接道路 → 新建道路 2–4
此时，所有枢纽之间都直接相连，无法再找到满足条件的三元组，操作停止。 总共新建道路数为 3。
样例 2 解释
初始没有任何道路（$M = 0$），则无法找到满足条件的三元组 $(X, Y, Z)$（因为需要存在两条现有道路 $X$–$Y$ 和 $Y$–$Z$）。 因此，新建道路数量为 0。
按照规则，最多可以新建 3 条道路：
1 与 2 有道路，2 与 3 有道路，但 1 与 3 没有直接道路 → 新建道路 1–3
1 与 3 有道路（上一步新建），3 与 4 有道路，但 1 与 4 没有直接道路 → 新建道路 1–4
2 与 1 有道路，1 与 4 有道路（上一步新建），但 2 与 4 没有直接道路 → 新建道路 2–4
此时，所有枢纽之间都直接相连，无法再找到满足条件的三元组，操作停止。 总共新建道路数为 3。
样例 2 解释
初始没有任何道路（$M = 0$），则无法找到满足条件的三元组 $(X, Y, Z)$（因为需要存在两条现有道路 $X$–$Y$ 和 $Y$–$Z$）。 因此，新建道路数量为 0。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？