int f(int x)
{
if(father[x]==x)return x;
return father[x]=f(father[x]);
}
void union1(int a,int b)
{
a=f(a),b=f(b);
if(a!=b)
father[b]=father[a];
}
并查集
为什么下面这种写法不行呢
int f(int x)
{
if(father[x]==x)return x;
return father[x]=f(father[x]);
}
void union1(int a,int b)
{
if(f(a)!=f(b))
father[b]=father[a];
}
两个代码不等价,前者不但计算了f(a)和f(b),而且改变了a b,后者没有改变a b。具体要看你完整的题目和代码。
void union1(int a,int b)
{
a=f(a),b=f(b);
if(a!=b)
father[b]=father[a];
}
这个把f(a)的返回值赋给了a,f(b)给了b;导致之后实际上是father[f(b)]=father[f(a)];
a=f(a),b=f(b);
if(a!=b)
father[b]=father[a];
第三句的a和b可能与第一行参数中的a和b不同了
但是你的写法是肯定相同的,所以不等价
因为地址和值的问题 第一种只比较值 int型 而第二种比较值以及地址