AT_abc302_e [ABC302E] Isolation

题目描述

最初有一个包含 $N$ 个顶点、$0$ 条边的无向图，每个顶点编号为 $1$ 到 $N$。
现在给出 $Q$ 个操作，请依次处理每个操作，并在每次操作后输出“没有与任何其他顶点通过边相连的顶点”的数量。

第 $i$ 个操作记作 $\mathrm{query}_i$，每个操作有以下两种类型之一：

• 1 u v：在顶点 $u$ 和顶点 $v$ 之间添加一条边。保证在该操作之前，$u$ 和 $v$ 之间没有边。
• 2 v：删除顶点 $v$ 与所有其他顶点之间的边（顶点 $v$ 本身不会被删除）。

输入格式

输入从标准输入读入，格式如下：

$N$ $Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

输出格式

输出共 $Q$ 行。
第 $i$ 行（$1\leq i\leq Q$）输出处理完第 $i$ 个操作后，“没有与任何其他顶点通过边相连的顶点”的数量。

输入输出样例 #1

输入 #1

3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2

输出 #1

1
0
0
1
0
3
1

输入输出样例 #2

输入 #2

2 1
2 1

输出 #2

2

说明/提示

限制条件

• $2\leq N\leq 3\times 10^5$
• $1\leq Q\leq 3\times 10^5$
• 对于类型 $1$ 的操作，$1\leq u,v\leq N$ 且 $u\neq v$
• 对于类型 $2$ 的操作，$1\leq v\leq N$
• 对于类型 $1$ 的操作，保证操作前 $u$ 和 $v$ 之间没有边
• 所有输入均为整数

样例解释 1

在第 $1$ 个操作后，顶点 $1$ 和顶点 $2$ 之间有一条边，只有顶点 $3$ 没有与任何其他顶点通过边相连。因此，第 $1$ 行输出 $1$。
在第 $3$ 个操作后，所有不同的两个顶点之间都有边相连，但第 $4$ 个操作会删除顶点 $1$ 与其他顶点之间的所有边，即删除顶点 $1$ 与顶点 $2$ 之间的边，以及顶点 $1$ 与顶点 $3$ 之间的边。
这样，顶点 $2$ 和顶点 $3$ 之间仍有边，但顶点 $1$ 不再与任何其他顶点相连。因此，第 $3$ 行输出 $0$，第 $4$ 行输出 $1$。

样例解释 2

在进行类型 $2$ 的操作之前，可能已经不存在任何与该顶点相连的边。

由 ChatGPT 4.1 翻译