rt,先给出一个我自己写的路径压缩的并查集:
int find(int x) {
return se[x] == x ? x : (se[x] = find(se[x]));
}
没用路径压缩:
int find(int x) {
return se[x] == x ? x : find(se[x]);
}
第二份代码可以进行尾调用优化,但是第一份应该不可以?
如果是的话,那么当数据较小,路径压缩带来的优化不明显时,会不会出现不用路径压缩反而更快的现象?
本人比较笨,想不清楚,所以发到讨论区问问各路大神 qwq