编程题
### 问题描述 小明进入一个神秘的空间,在这个空间的下面往往天上看去,可以看到天上有 $n$ 个星星并且有 $m$ 条线连接着他们。神奇的是这 $n$ 个星星通过这 $m$ 条线构成了一个无向联通图(**连通图指的是任选两个点都能通过边互相到达**)。 小明看着天上的星星,逐渐陷入了沉思,他在想这幅由星星构成的无向图中是否存在一个特殊点,如果将这个特殊点删除之后,剩下的 $n-1$ 个点就无法构成一个联通图了。聪明的你能帮小明计算一下特殊点共有几个吗。 ### 输入格式 第一行,包含两个正整数 $n$ $(1\leq n\leq 10^5)$ 和 $m$ $(n-1\leq m\leq \frac{n\times (n-1)}{2})$ ,代表天上有 $n$ 颗星星和 $m$ 条连接星星的边。 接下来 $m$ 行,每行两个正整数 $u$ ,$v$ $(1\leq u,v\leq n)$ 。代表顶点 $u$ 和顶点 $v$ 之间有一条无向边将这两个顶点相连。 ### 输出格式 一行,包含一个正整数,代表这个图中特殊点的总数。 ### 样例输入 ``` 5 4 1 2 2 3 1 4 4 5 ``` ### 样例输出 ``` 3 ``` ### 样例解释 在样例中,当我们删掉编号为 $1$ 或者编号为 $2$ 或者编号为 $4$ 的节点时,剩下的节点将会无法构成一个连通图,故这个图中特殊点总数为 $3$ 。
查看答案
赣ICP备20007335号-2