AcWing 238.银河英雄传说 (边带权并查集)

题意:有\(n\)列,有\(T\)条指令,若指令格式为\(M\),则将第\(i\)号的所有战舰移到第\(j\)号所在列的后面,若指令格式为\(C\),询问\(i\)和\(j\)是否在同一列,如果在,问他们之间隔了多少战舰.
题解:带权并查集的模板题,\(d\)数组表示某个节点到祖先的距离,\(s\)数组表示集合的子节点个数,当进行合并时,我们可以让\(i\)的祖先到另外一个集合的祖先距离为\(s[fb]\),即\(d[fa]=s[fb]\),然后\(j\)所在集合的元素个数增加,\(s[fb]+=s[fa]\),然后合并即可.我们在\(find\)函数压缩路径时,要把每个点到祖先路径上的边权累加起来,如果并查集的原理你理解的话,这里并不难想.最后查询距离的时候要记得用和\(0\)取个最大值即可.

代码:

int n;

int p[N],s[N],d[N];

int find(int x){

	if(p[x]!=x){

		int root=find(p[x]);

		d[x]+=d[p[x]];

		p[x]=root;

	}

	return p[x];

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n;

    rep(i,1,30010){

    	p[i]=i;

    	s[i]=1;

    }

    rep(i,1,n){

    	char op;

    	int a,b;

    	cin>>op>>a>>b;

    	if(op=='M'){

    		int fa=find(a);

    		int fb=find(b);

    		d[fa]=s[fb];

    		s[fb]+=s[fa];

    		p[fa]=fb;

    	}

    	else{

    		int fa=find(a);

    		int fb=find(b);

    		if(fa!=fb) cout<<-1<<'\n';

    		else cout<<max(0,abs(d[b]-d[a])-1)<<'\n';

    	}

    }

    return 0;

}

巴特西

AcWing 238.银河英雄传说 (边带权并查集)

最新文章

热门文章