07680. 加边判环 · 林老师的题库

题目描述

工地上有 $n$ 个作业点，编号为 $1$ 到 $n$ ，一开始点与点之间没有任何道路。接下来依次给出 $m$ 条候选道路 $(u_{i}, v_{i})$ ，并按下面的规则决定是否采纳：

如果当前图中 $u_{i}$ 与 $v_{i}$ 已经连通（即采纳这条边会形成环），就输出 Yes，并跳过这条道路，图保持不变；
否则采纳这条道路，输出 No。
特别地，当 $u_{i} = v_{i}$ 时，这条自环边会形成环，应当输出 Yes 并跳过。所有 $m$ 条道路处理完毕后，再输出一行，表示最终图中连通块的个数。

第一行包含两个整数 $n, m$ 。

接下来 $m$ 行，每行包含两个整数 $u_{i}, v_{i}$ ，表示第 $i$ 条待加入的边。

输出共 $m + 1$ 行。

前 $m$ 行依次对应 $m$ 条边：若这条边被跳过则输出 Yes，若这条边被加入则输出 No。

最后一行输出一个整数，表示处理完所有边之后图中连通块的个数。

No
No
Yes
Yes
No
No
1

第 $i$ 条边	加入前 $u_{i}$ 与 $v_{i}$ 是否连通	输出	加入后的连通块
$(1, 2)$	否	`No`	${1, 2}, {3}, {4}, {5}$
$(2, 3)$	否	`No`	${1, 2, 3}, {4}, {5}$
$(3, 1)$	是	`Yes`	不变
$(4, 4)$	是（自环）	`Yes`	不变
$(4, 5)$	否	`No`	${1, 2, 3}, {4, 5}$
$(1, 5)$	否	`No`	${1, 2, 3, 4, 5}$

最后一条边把两个连通块连成一个，所以第六次输出的是 No；最终图中有 $1$ 个连通块，最后一行输出 $1$ 。

对于全部测试数据：