编程题
### 问题描述 一座城市的电网由 $n$ 个电站和它们之间的 $m$ 条连接线组成,你是负责维护电网稳定运行的工程师。这一天你突然发现,当这个电网中的某些电站出现故障时,可能会导致两个或多个区域的电网被断开,从而使这些区域失去电力供应。这样的节点被称为高危节点。 为了保证城市电力的稳定供应,你现在需要确定哪些电站是电网的高危节点,以方便接下来为其准备备用方案。由于城市电网的规模庞大,手工判断每一个节点的重要性是不现实的。因此你打算使用计算机程序来确定哪些电站是电网的关键节点。 现在给出一个表示电网的图,你能编写一个程序找出所有的高危节点吗? ### 输入格式 第一行输入两个整数 $n$ 和 $m$,分别表示这座城市电站的数量和电站间连线的数量。 接下来 $m$ 行,每行两个整数 $a_i$ 和 $b_i$,表示编号为 $a_i$ 和 $b_i$ 的电站之间存在连接线路。电站节点的编号从 $1$ 到 $n$。 题目保证输入的图为连通图,且两个电站之间可能存在多条连线。 ### 输出格式 输出有多行。第一行输出一个整数 $t$,表示当前的电网中存在 $t$ 个高危节点。 接下来的 $t$ 行,每行输出两个整数 $x_i$ 和 $y_i$,表示编号为 $x_i$ 的节点是高危节点,并且当该电站失效后,城市电网将被分为 $y_i$ 个不连通的区域。 如果电网中不存在高危节点,则在一行中输出一个 $0$。 ### 样例输入 ``` 5 4 1 3 2 3 3 4 4 5 ``` ### 样例输出 ``` 2 3 3 4 2 ``` ### 测评数据规模 $1\le n\le 10^4$,$1\le m\le 10^5$。
查看答案
赣ICP备20007335号-2