AT_unionfind_a Union Find

[problemUrl]: https://atcoder.jp/contests/atc001/tasks/unionfind_a 本题为讲座用题目。页面底部附有题解。 考虑一个有 $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，素集合数据结构）](https://www.slideshare.net/secret/CIWAduFPvzGrrE "Union find(素集合データ構造)")** 来自 **[AtCoder Inc.](http://www.slideshare.net/chokudai)** ### 样例解释 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 翻译