提交记录:P221354442,P221354460
代码区别:
前者:
if(opt=='E') {
relation[findroot(q+1000)]=findroot(p);
relation[findroot(p+1000)]=findroot(q);
}
else{
relation[findroot(p)]=findroot(q);
}
后者:
pp=findroot(p),pq=findroot(q),np=findroot(p+1000),nq=findroot(q+1000);
if(opt=='E') {
relation[nq]=pp;
relation[np]=pq;
}
else{
relation[pp]=pq;
}
relation数组用于存储所在集合,findroot()函数用于寻找该集合的“根”并进行路径压缩。
下载测试点后发现在#11上,后者代码的relation数组在57号位上会存储57而非前者的408,导致结果比正解高1。
尝试过不进行路径压缩的写法但结果未受影响。
不清楚具体为什么。个人认为两种写法的本质相同,但实际导致了不一样的结果。
希望能有大佬解答。