关于 FIND_ROOT 的必要性
查看原帖
关于 FIND_ROOT 的必要性
411103
Patricky楼主2022/6/9 20:18

在网上看到一个版本 link cut 两种操作均未使用 find_root 的操作。有两个问题:

  1. 这样的 合理性
  2. 如果合理,为什么 合理?

求助!!

这里是提交记录 record,请留意注释部分。

  • Link
// void link(int x, int y) { mkroot(x), f[x] = y, access(x); }
void link(int x, int y) {
  mkroot(x);
  if (root(y) != x) {
    f[x] = y; 
  }
}
  • Cut
// void cut(int x, int y) {
//   mkroot(x), access(y), splay(y), f[son[y][0]] = 0, son[y][0] = 0, up(y);
// }
void cut(int x, int y) {
  mkroot(x);
  if (root(y) == x && f[y] == x && !son[x][0]) {
    son[x][1] = f[y] = 0, up(x);
  }
}
2022/6/9 20:18
加载中...