@[DELA](/user/822718) 哥们我建议你删几个贴 别在本题板块下刷屏。
by Yusani_huh @ 2023-09-19 10:08:55
如果真调不出来了可以考虑找篇题解拍一拍。这题数据应该不算难造。
by Yusani_huh @ 2023-09-19 10:10:33
@[DELA](/user/822718) 就你帖子最上面发的程序而言
我给你调出来了问题有如下:
①`merge` 中比较合并元素的优先级中,应当为 `v[x] < v[y]||v[x]==v[y]&&x<y`。
②`merges` 需要记录当且节点 `x` 的兄弟节点,因为后面还有重新赋值,导致合并出错。
③`op==1` 的情况,应当判断是否可以合并。`rt[find(x)] = t` 中的 `x` 应当改成 `y`,原因是并查集合并的时候是把 `x` 并到 `y` 上 `y` 的根作父亲。
④`op==2` 的情况,如果节点被删除应当 `continue;` 否则后面一堆可能会造成负面结果。
```cpp
#include <iostream>
using namespace std;
int v[100005], child[100005], sibling[100005], f[100005], rt[100005];
bool del[100005];
int merge(int x, int y) {
if (!x || !y) return x+y;
if (v[x] < v[y]||v[x]==v[y]&&x<y)
return sibling[y] = child[x], child[x] = y, x;
else return sibling[x] = child[y], child[y] = x, y;
}
int merges(int x) {
if (!x && !sibling[x]) return x;
int tt = sibling[sibling[x]],t=sibling[x];
sibling[x] = sibling[sibling[x]] = 0;
return merge(merge(x, t), merges(tt));
}
int find(int x) {
return f[x] == x? x: f[x] = find(f[x]);
}
int main() {
int n, m, op, x, y, t;
cin >> n>> m;
for (int i=1; i<=n; i++) cin >> v[i], f[i] = i, rt[i] = i;
for (int i=1; i<=m; i++) {
cin >> op>> x;
if (op == 1)
{
cin >> y;
if(del[x]||del[y]||find(x)==find(y))continue;
t = merge(rt[find(x)], rt[find(y)]);
f[find(x)] = find(y), rt[find(y)] = t;
}
else
{
cout << (del[x] ? -1 : v[rt[find(x)]]) << endl;
if(!del[x])del[rt[find(x)]] = true, rt[find(x)] = merges(child[rt[find(x)]]);
}
}
}
```
by Terrible @ 2023-09-19 10:42:02
另外建议删除本题讨论区除了本帖外的其他捞题帖。@[DELA](/user/822718)
by Terrible @ 2023-09-19 10:44:45
@[FatOldEight](/user/329177) orz,感激不尽
by DELA @ 2023-09-19 11:32:31
@[Terrible](/user/195942) orz,还有几个问题想问一下:
> 原因是并查集合并的时候是把 x 并到 y 上 y 的根作父亲。
这里的并查集只用来维护节点的连通性,`find(x)` 和 `find(y)` 的值不应该是一样的嘛
> merge 中比较合并元素的优先级中,应当为 `v[x] < v[y]||v[x]==v[y]&&x<y`。
为什么要根据结点编号合并呢,当 x 和 y 的权值相等的时候往哪边合并有什么区别吗?
by DELA @ 2023-09-19 11:37:48
@[Yusani_huh](/user/239895) 能拍的话我早就拍了
by DELA @ 2023-09-19 11:38:06
哦
> 若有多个最小数,优先删除先输入的
,没事了。
by DELA @ 2023-09-19 11:53:10
@[DELA](/user/822718) 先合并再查父亲啊?那没事了。
by Terrible @ 2023-09-19 11:55:16
(因为我自己写的是只查一遍 `x` 和 `y` 的父亲的那种。)
by Terrible @ 2023-09-19 11:56:37