P9 【模板】可撤销并查集
时间限制 2000 ms
空间限制 128 MB
难度
提交次数 256
通过次数 76
未做过本题

题目描述

给定n个结点,q次询问,每次询问分为三类:

1 \space x\space y :可以选择将x, y两个点连通,如果已经连通则不操作。

2 :撤销上一次的操作(若全部撤销完了则不操作)。

3 \space x \space y:询问x, y是否连通,如果是则输出"YES",反之输出"NO",请注意都是大写字母,不包含引号。

输入描述

第一行两个整数n(1 \le n \le 10^6), q(1 \le q \le 10^5),分别表示结点的个数和询问的次数。

接下来q行,每行一个询问op \space x \space y(1 \le op \le 3, 1 \le x, y \le n),当op=2时,没有x, y

输出描述

对于每一个3询问,一行一个字符串("YES" 或 "NO")表示结果。

输入样例1

复制代码
4 5
1 1 2
1 1 3
3 2 3
2
3 2 3

输出样例1

复制代码
YES
NO

本题在《算法中级课》中有详细讲解:https://www.starrycoding.com/course/2

快捷菜单
在线运行
语言:
登录后可在线运行与提交。