← 返回题目列表

Codeforces · 977/E

E. 循环分量

中文机器翻译题面 查看原题

给你一个无向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。您的任务是找到循环的连接组件的数量。

以下是图论的一些定义。

无向图由两组组成:节点集(称为顶点)和边集。每条边连接一对顶点。所有边都是双向的(即,如果顶点 $$$a$$$ 与顶点 $$$b$$$ 连接,则顶点 $$$b$$$ 也与顶点 $$$a$$$ 连接)。一条边不能将顶点与其自身相连,一对顶点之间最多有一条边。

当且仅当沿着连接 $$$u$$$ 和 $$$v$$$ 的边至少有一条路径时,两个顶点 $$$u$$$ 和 $$$v$$$ 属于同一连通分量。

连接的组件是一个循环当且仅当它的顶点可以通过以下方式重新排序:

- 第一个顶点通过边与第二个顶点连接,
- 第二个顶点通过边与第三个顶点连接,
- ...
- 最后一个顶点通过边与第一个顶点连接,
- 循环的所有描述的边缘都是不同的。

循环不包含除上述之外的任何其他边。根据定义,任何环都包含三个或更多顶点。

有 $$$6$$$ 个连通分量,其中 $$$2$$$ 是循环:$$$[7, 10, 16]$$$ 和 $$$[5, 11, 9, 15]$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — 顶点和边的数量。

以下 $$$m$$$ 行包含边:边 $$$i$$$ 作为一对顶点给出 $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$)。给定图中没有多条边,即对于每对 ($$$v_i, u_i$$$),边列表中没有其他对 ($$$v_i, u_i$$$) 和 ($$$u_i, v_i$$$)。

输出

打印一个整数 — 连接分量的数量,也是循环。

示例

输入 #1

5 4
1 2
3 4
5 4
3 5

输出 #1

1

输入 #2

17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6

输出 #2

2

注意

在第一个示例中,只有组件 $$$[3, 4, 5]$$$ 也是一个循环。

上图对应于第二个示例。