沈先生 @ 2019-11-13 22:25:21
这里find的记忆化
int find(int x)
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
} 就算加了记忆化,只要f[x]!=x,不还是需要把每个数据递归一遍吗....我想问这个是如何起到记忆作用的
by Lacrymabre @ 2019-11-13 22:28:18
f[x]=find(f[x]);
by 一濑红莲 @ 2019-11-13 22:32:56
下一次调用就不用把每个数据递归一次了
by SomeyaMako @ 2019-11-13 22:35:58
@沈先生 相当于直接让某个人父亲的所有儿子和父亲平起平坐，给原来的爷爷当儿子，然后递归处理这种情况
by Minecraft万岁 @ 2019-11-13 22:39:40
int find(int x)//这样写貌似不用担心栈溢出
{
int r=x;
while(f[r]!=r) r=f[r];
int i=x,j;
while(i!=r) j=f[i],f[i]=r,i=j;
return r;
} by Belarus @ 2019-11-13 22:42:19
@沈先生 康康这个
戳我
by 沈先生 @ 2019-11-14 01:46:33
@爆零_自动机 谢谢大佬
by 沈先生 @ 2019-11-14 01:46:44
@一濑红莲 谢谢大佬
by 沈先生 @ 2019-11-14 01:46:58
@SomeyaMako 谢谢大佬
by 沈先生 @ 2019-11-14 01:47:09
@Minecraft万岁 谢谢大佬
by 沈先生 @ 2019-11-14 01:47:34
@Belarus 谢谢大佬!!