P1196 [NOI2002]银河英雄传说
题意
略(中文)
思路
边带权并查集,用front[i]记录i到根节点之间有多少艘战舰,num[i]表示第i列有多少艘战舰.
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=3e4+10;
int num
[maxn
],front
[maxn
],fa
[maxn
];
int find(int x
){
if(x
==fa
[x
]) return x
;
int fx
=find(fa
[x
]);
front
[x
]+=front
[fa
[x
]];
return fa
[x
]=fx
;
}
int main(){
int _
;scanf("%d",&_
);
for(int i
=1;i
<=30000;i
++){
fa
[i
]=i
;
front
[i
]=0;
num
[i
]=1;
}
while(_
--){
char s
[2];
int x
,y
;
scanf("%s%d%d",s
,&x
,&y
);
int fx
=find(x
),fy
=find(y
);
if(s
[0]=='M'){
front
[fx
]+=num
[fy
];
num
[fy
]+=num
[fx
];
num
[fx
]=0;
fa
[fx
]=fy
;
}
if(s
[0]=='C'){
if(fx
!=fy
) puts("-1");
else printf("%d\n",abs(front
[x
]-front
[y
])-1);
}
}
return 0;
}
