略优化的并查集模板
略优化的并查集模板
之前写过一个题，是并查集+搜索，思路很明确但是不论我用什么我目前已知的方法去写这个题都一直TLE，最后问了学长才知道在做并归操作的时候通过维护树高可以优化最后所得树的结构。
闲话不多，还是结合注释看代码吧。
const int maxn = (int)1e5+7;
int pre[maxn],height[maxn];
//pre就不解释了，height是当前树高
int Find(int x) {//while以及附帶路徑壓縮的版本，遞歸在數據量比較大的時候可能爆
if(x==pre[x]) return x;
int p=x,q;
while(x!=pre[x]) x=pre[x];
while(p!=pre[p]) {
q=pre[p];
pre[p]=x;
p=q;
}
return x;
}
void Add(int i, int j) {
int x=Find(i),y=Find(j);
if(x==y) return ;
if(height[x]<height[y]) pre[x]=y;
else {
if(height[x]==height[y]) height[x]++;
pre[y]=x;
}
return ;
}智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。