#P18681. Disjoint Set Union
Disjoint Set Union
Disjoint Set Union
最近,小青鱼正在学习并查集(DSU)。它是一种强大的数据结构,可以向图中加边,并判断两个顶点是否连通。
并查集维护由n个顶点组成的有根森林。每个顶点x(1≤x≤n)有唯一的父亲f[x];如果x=f[x],x就是所在树的根。最初每个顶点各自构成一棵树,即所有f[x]=x。
并查集有两种基本操作:
find(x):返回x所在树的根。unite(x,y):先计算x′=find(x)、y′=find(y)。若x′=y′则不再合并;否则令f[x′]=y′。
为加速操作,小青鱼使用了路径压缩:每次调用find(x),都将从x到根路径上每个顶点的父亲直接改为该根。具体过程如下。注意即使unite的两点已经连通,也会先执行两次find所产生的路径压缩。
函数 find(f, x):
如果 x = f[x]:
返回 x
f[x] ← find(f, f[x])
返回 f[x]
过程 unite(f, x, y):
x ← find(f, x)
y ← find(f, y)
如果 x ≠ y:
f[x] ← y
小青鱼非常喜欢并查集。他从所有f[i]=i开始,进行了任意多次(也可以零次)以下操作:选择1≤x≤n并调用find(x),或者选择1≤x,y≤n并调用unite(x,y)。现在他将这些操作后的数组f交给你。
另给出长度同样为n的目标数组g。你希望继续使用上述并查集操作,将f变为g,即最后对每个1≤i≤n都有f[i]=g[i]。判断能否做到;若能,给出一组操作方案。
输入格式
第一行一个整数T(1≤T≤100000),表示测试用例数。每个测试用例:
- 第一行一个整数n(3≤n≤1000)。
- 第二行n个整数f1,…,fn,表示小青鱼操作后的父数组。保证f能由上述操作生成。
- 第三行n个整数g1,…,gn,表示目标父数组。父亲编号对应1至n的顶点。
所有测试用例的n²之和不超过5000000。g可能不能由这些操作得到,需要由你的程序判断。
输出格式
对每个测试用例:若不能将f变为g,输出一行NO。否则:
- 第一行输出
YES。 - 第二行输出整数m(0≤m≤2n²),表示操作数。
- 接下来m行,每行输出一种操作:
1 x表示调用find(x),2 x y表示调用unite(x,y)。操作中的顶点编号均须在1至n之间。
可以输出任意合法方案。可以证明:若存在方案,就存在操作数不超过2n²的方案。
样例输入
5
3
1 2 3
2 2 3
4
1 2 3 3
1 1 1 2
5
1 2 3 4 5
2 3 4 5 5
5
1 1 1 1 1
1 2 3 4 5
6
1 2 2 4 5 6
1 1 5 1 4 2
样例输出
YES
1
2 1 2
YES
4
2 3 2
1 4
2 2 1
1 3
YES
4
2 1 2
2 1 3
2 2 4
2 3 5
NO
YES
7
2 6 2
2 2 5
1 3
2 2 4
1 2
2 2 1
1 2
样例输出为原题的一种合法方案,操作方案不唯一。本题采用精确特殊判题,不能按输出文本逐字比较。