题目描述
如何理解find函数中的寻找根结点和路径压缩?
解答
原模板:
int find (int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
可以把y总的模板拆分一下,会方便理解些
int find (int x)
{
if(x != p[x])
{
int t = find(p[x]); //寻找根结点,找到后回溯
p[x] = t; //路径压缩
}
return p[x];
}
也就不难理解Acwing 240 食物链这道题的find函数了:
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]); //寻找根结点,找到后回溯
d[x] += d[p[x]]; //回溯中更新到根结点的距离
p[x] = t; //路径压缩
}
return p[x];
}
谢谢,很有帮助!
解释的很好!!!
就我一个人是认为是白看没懂吗
解释的真不错
女少
哈哈哈哈 理解了 谢谢~
# 女子
实不相瞒,我是用的向量来理解的食物链
请问向量是咋理解的。。。