P11976 [KTSC 2021] 通信网络 / communication
题目背景
本题翻译自 [2021년도 국제정보올림피아드 대표학생 선발고사](https://www.ioikorea.or.kr/archives/ioitst/2021/) 1차 선발고사 [#2 통신망](https://assets.ioikorea.or.kr/ioitst/2021/1/communication/communication_statement.pdf)。
**请注意，你不需要也不应该实现 `main` 函数。具体实现方式见【实现细节】部分。**
提交时，请在程序开头添加如下内容，并且无需引用 `communication.h`：
```cpp
#include
#include
std::vector find_num_critical(int N, std::vector< std::pair > E);
```
**警告：滥用本题评测一次即可封号。**
题目描述
通信网络由 $N$ 台计算机和 $M$ 条线路组成。计算机编号为 $1$ 到 $N$。每条线路连接两台不同的计算机，使得它们之间支持双向通信。如果网络中任意两台计算机都可以通过一条或多条线路通信，则称网络是连通的；否则称网络是断开的。
对于网络中的一条线路 $c$，其危险度定义如下：
- 对于每台计算机 $i$，如果移除 $i$ 后剩余网络断开，则称 $i$ 为危险计算机。
- 初始网络中移除线路 $c$ 后，危险计算机的数量即为 $c$ 的危险度。
请编写一个程序，计算每条线路的危险度。
### 实现细节
你需要实现以下函数：
```cpp
vector find_num_critical(int N, vector< pair > E)
```
- 该函数仅被调用一次。
- 参数 $N$ 表示计算机的数量。
- 参数 $E$ 是一个大小为 $M$ 的数组，每个元素表示一条线路，由两个不同的计算机编号组成。
- 返回一个长度为 $M$ 的整数数组，表示每条线路的危险度，顺序与 $E$ 一致。
在提交的源代码的任何位置均不得调用标准输入输出操作。
输入格式
示例评测程序的输入格式如下：
- 第 $1$ 行：$N \ M$
- 第 $1+i$ 行（$1 \leq i \leq M$）：$a_i \ b_i$
$a_i, b_i$ 表示 $a_i$ 号计算机与 $b_i$ 号计算机通过线路连接（$1 \leq i \leq M$）。
输出格式
示例评测程序的输出格式如下：
- 第 $1$ 行：函数 `find_num_critical` 返回的数组
请注意，示例评测程序可能与实际评测程序有所不同。
说明/提示
### 约束条件
- $2 \leq N \leq 250\,000$
- $1 \leq M \leq 1\,000\,000$
- 每条线路连接两台不同的计算机。
- 可能存在多条线路连接同一对计算机。
- 初始网络是连通的。
### 子任务
1. （$5$ 分）
- $N \leq 200$
- $M \leq 500$
2. （$11$ 分）
- $N \leq 1\,000$
- $M \leq 2\,500$
3. （$7$ 分）
- $N = M$
4. （$13$ 分）
- 对于满足 $k \geq 2$ 的互不相同的计算机 $v_1, v_2, \cdots, v_k$ 和 $k$ 条互不相同的通信线路 $c_1, c_2, \cdots, c_k$，若线路 $c_i$ 连接计算机 $v_i$ 和 $v_{i+1}$（其中 $1 \leq i \leq k-1$），且线路 $c_k$ 连接计算机 $v_k$ 和 $v_1$，则称这 $k$ 条线路 $c_1, c_2, \cdots, c_k$ 构成一个**环（cycle）**。两个环相同当且仅当它们所包含的线路集合完全一致。
- 在通信网络中，对于任意线路 $c$，包含 $c$ 的环最多存在一个。
5. （$25$ 分）
- $N \leq 8\,000$
- $M \leq 250\,000$
6. （$29$ 分）
- $N \leq 100\,000$
- $M \leq 250\,000$
7. （$10$ 分）
- 无额外约束。
## 评分标准
只有 `find_num_critical` 函数返回的序列长度等于 $M$，且返回序列的所有元素与标准答案序列完全一致时，该组测试数据才会被判定为正确。
### 示例
- 当 $N = 5$ 且线路集合 $E = [ [1, 5], [5, 2], [2, 3], [2, 4], [2, 5] ]$ 时，评分系统将调用函数：
```cpp
find_num_critical(5, [ [1,5], [5,2], [2,3], [2,4], [2,5] ])
```
初始通信网络结构如下：
例如，当移除连接计算机 $1$ 和 $5$ 之间的线路后，网络变为：
此时危险计算机是 $2, 3, 4, 5$ 号。需注意 $1$ 号计算机被移除时剩余网络仍保持连通，因此不属于危险计算机。
当移除任意一条连接计算机 $2$ 和 $5$ 的线路后，网络变为：
此时危险计算机是 $2$ 号和 $5$ 号。
`find_num_critical` 函数应返回序列 $[4, 2, 4, 4, 2]$。
此示例满足所有子任务的约束。