AT_unionfind_a.Union Find

本题为讲座用题目。页面底部附有题解。

考虑一个有 $N$ 个顶点的无向图，该图不一定是简单图。初始状态下，图中只有顶点，没有任何边，所有顶点都是孤立的。接下来会给出 $Q$ 次如下两种类型的操作：

• 连接操作：在顶点 $A$ 和顶点 $B$ 之间添加一条边。
• 查询操作：判断顶点 $A$ 和顶点 $B$ 是否连通。如果连通则输出 Yes，否则输出 No。

请按顺序处理所有操作，并对每个查询操作输出答案。需要注意的是，可能会多次添加同一条边，也可能会添加自环。

顶点 $A$ 和顶点 $B$ 连通，指的是可以通过若干条边从 $A$ 到达 $B$。当 $A$ 和 $B$ 是同一个顶点时，视为连通。由于图是无向图，连接操作在 $A$ 和 $B$ 之间添加边后，$A$ 可以到达 $B$，$B$ 也可以到达 $A$。

输入通过标准输入给出，格式如下：

$N$ $Q$
$P_1$ $A_1$ $B_1$
$P_2$ $A_2$ $B_2$
$\vdots$
$P_Q$ $A_Q$ $B_Q$

• 第 $1$ 行包含两个整数 $N\ (1 \leq N \leq 100\,000)$ 和 $Q\ (1 \leq Q \leq 200\,000)$，分别表示顶点数和操作数，以空格分隔。
• 接下来的 $Q$ 行，每行包含三个整数 $P_i\ (0 \leq P_i \leq 1)$、$A_i$、$B_i\ (0 \leq A_i, B_i \leq N-1)$，以空格分隔。
  • 当 $P_i = 0$ 时，表示连接操作。
  • 当 $P_i = 1$ 时，表示查询操作。

对于每个查询操作，输出一行答案。每次输出后需换行。

题解

并查集（Union Find，素集合数据结构） 来自 AtCoder Inc.

样例解释 1

操作按如下顺序执行：

• 第 $1$ 次操作，将顶点 $1$ 和顶点 $2$ 连接。
• 第 $2$ 次操作，将顶点 $3$ 和顶点 $2$ 连接。
• 第 $3$ 次操作，查询顶点 $1$ 和顶点 $3$ 是否连通。它们已连通，输出 Yes。
• 第 $4$ 次操作，查询顶点 $1$ 和顶点 $4$ 是否连通。它们未连通，输出 No。
• 第 $5$ 次操作，将顶点 $2$ 和顶点 $4$ 连接。
• 第 $6$ 次操作，查询顶点 $4$ 和顶点 $1$ 是否连通。它们已连通，输出 Yes。
• 第 $7$ 次操作，将顶点 $4$ 和顶点 $2$ 连接。它们已连通，但允许出现多重边。
• 第 $8$ 次操作，将顶点 $0$ 和顶点 $0$ 连接。它们是同一个顶点，也允许出现自环。
• 第 $9$ 次操作，查询顶点 $0$ 和顶点 $0$ 是否连通。同一个顶点总是连通的，输出 Yes。

由 ChatGPT 4.1 翻译