不懂就问,救救孩子吧
  • 板块灌水区
  • 楼主Cuiyi_SAI
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/12/19 13:18
  • 上次更新2023/10/28 14:05:49
查看原帖
不懂就问,救救孩子吧
488775
Cuiyi_SAI楼主2021/12/19 13:18

就这题,一直过不了,只对了#2,这是原来的 find 函数:

int find(int x)
{
	if(fa[x]==x) return x;
	dis[x]+=dis[fa[x]];
	return fa[x]=find(fa[x]);
}

但是我看了看讨论版后改了一下,变成这样:

int find(int x)
{
	if(fa[x]==x) return x;
	int t=find(fa[x]);  
    //唯一的改变就是这里用了一个变量存起来
	dis[x]+=dis[fa[x]];
	fa[x]=t;
	return fa[x];
}

就直接AC了,请问这是为什么啊?我普通并查集按照之前的写法写也没问题啊,难道说带权并查集一定要额外变量存?

2021/12/19 13:18
加载中...