关于代码中按秩合并的一个问题
查看原帖
关于代码中按秩合并的一个问题
79075
mzgwty楼主2021/1/28 16:56

RT,RT,为什么把大于改成小于就能过,不然就WA了呢

按理来说这个改成小于不是就变成深度大的并到深度小的上去了,不是应该T吗(但它过了)

inline void merge(int k,int x,int y) {
	int a=op[x],b=op[y],t1=x,t2=y;
	if(d[a]>d[y]) swap(a,y);
	if(a&&y) s.push(data(a,k,d[a]==d[y])),d[y]+=d[a]==d[y],f[a]=y;
	w.push(QWQ(t1,op[t1],k)),op[t1]=t2;
	if(d[b]>d[x]) swap(b,x);
	if(b&&x) s.push(data(b,k,d[b]==d[x])),d[x]+=d[b]==d[x],f[b]=x;
	w.push(QWQ(t2,op[t2],k)),op[t2]=t1;
}

inline void work(int k,int x,int y) {
	int r1=find(x),r2=find(y);
	if(r1==r2) return ok[k]=1,void();
	merge(k,r1,r2);
}
inline void merge(int k,int x,int y) {
	int a=op[x],b=op[y],t1=x,t2=y;
	if(d[a]<d[y]) swap(a,y);
	if(a&&y) s.push(data(a,k,d[a]==d[y])),d[y]+=d[a]==d[y],f[a]=y;
	w.push(QWQ(t1,op[t1],k)),op[t1]=t2;
	if(d[b]<d[x]) swap(b,x);
	if(b&&x) s.push(data(b,k,d[b]==d[x])),d[x]+=d[b]==d[x],f[b]=x;
	w.push(QWQ(t2,op[t2],k)),op[t2]=t1;
}

inline void work(int k,int x,int y) {
	int r1=find(x),r2=find(y);
	if(r1==r2) return ok[k]=1,void();
	merge(k,r1,r2);
}
2021/1/28 16:56
加载中...