为什么不能用Lca判断2点 是否在同一块呢?
查看原帖
为什么不能用Lca判断2点 是否在同一块呢?
188970
Twiter_ln楼主2023/10/26 20:31

为什么不能用Lca判断2点 是否在同一块呢?

∵dfs(1)∵dfs(1) 的时候,不会 dfsdfs 到另一块,所以 LcaLca 的 fa[x][0]fa[x][0] 的判断不会执行到,无法 return−1。return-1。

inline int Lca(int x, int y) {
   if(dep[x] > dep[y]) swap(x, y);
   if(dep[x] == dep[y]) goto L;
   int tx, ty;
   for(int j=20;j>=0;--j) {
   	ty = fat[y][j];
   	if(ty == 0) continue;
   	if(dep[ty] >= dep[x]) y = ty;
   	if(dep[y] == dep[x]) break;
   }
   L:
   if(x == y) return d[x];
   for(int j=20;j>=0;--j) {
   	tx = fat[x][j];
   	ty = fat[y][j];
   	if(tx==0 || ty==0) continue;
   	if(tx == ty) continue;
   	x = tx;
   	y = ty;
   }
   
   // if(fat[x][0] != fat[y][0]) return -1;
   // 此处 在输入处,使用 并查集 判断 !
   
   return d[fat[x][0]];
}
2023/10/26 20:31
加载中...