不是VIP会员,不能显示答案

题目解答

题目:
(并查集)舰队司令莱因哈特率领十万余艘战规出征。名将杨威利组织麾下三万晚战舰迎敌。在这次决战中,他将巴米利恩星域战场划分成30000列,每列依次编号为1,2,...,30000之后,他把自己的战舰也依次编号为1,2,...,30000,让第i号战舰处于第i列(i=1,2,...,3000)。这是初始阵形。杨威利会多次发布合并指令,将大部分战战舰集中在某几列上,实施密集攻击。合并指令为Mi,j,含义为第i号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。在杨威利发布指令调动舰队的同时,莱因哈特也会发出一些询问指令:Ci,j。该指令意思是,询问电脑,杨威利的第i号战舰与第j号战舰当前是否在同一列中, 如果在同一列中,那么它们之间布置有多少战舰。你被要求编写程序分析杨威利的指令,以及回答莱因哈特的询问。



#include <bits/stdc++.h>

using namespace std;

int f[30001], front[30001],num[30001],x,y,i,j, n, T,ans;

char ins;

int find(int n) {

if (fa[n] == n)

return fa[n];

int fn = find(fa[n]);

___(1)___;

return fa[n] = fn;

}

int main() {

cin>> T;

for(i=1; i<=30000; ++i) {

fa[i]= i;

___(1)___;

num[i]=1;

}

while(T--) {

cin>> ins>> x>> y;

int fx=find(x);

int fy=find(y);

if (ins == 'M') {

front[fx] += num[fy];

fa[fx]=ty;

___(3)___;

num[fx]=0;

}

if(ins =='C') {

if(___(4)___)

cout <<"-1" << endl;

else

cout <<___(5)___<< endl;

}

}

return 0;

}




选择题

1) ①处应填( )

2) ②处应填( )

3) ③处应填( )

4) ④处应填( )

5) ⑤处应填( )
考点:
分析:
解答:
评论:
老师: