全wa 但第一个点自测是对的 求助
查看原帖
全wa 但第一个点自测是对的 求助
615557
qinmanling123楼主2024/8/20 16:17
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 3e4+1;
int T,fa[N],sum[N],t[N];
char c;
int i,j;

int find_f(int x){
	if(x == fa[x]){
		return x;
	}
	int fx = fa[x],fy = find_f(fa[x]);
	fa[x] = fy;
	t[x] += t[fx];
	return fy; 
}

void join(int x,int y){
	int fx = find_f(x);
	int fy = find_f(y);
	fa[fy] = fx;
	t[fy] = sum[fx];
	sum[fx] += sum[fy];
	sum[fy] = 0;
}

int main(){
	scanf("%d",&T);
	for(int k = 1;k <= N;k++){
		fa[k] = k;
		sum[k] = 1;
	}
	for(int k=1;k<=T;k++){
		cin>>c;
		scanf("%d %d",&i,&j);
		if(c == 'M'){
			join(j,i);
		}else{
			if(find_f(i) != find_f(j)){
				printf("-1\n");
			}else{
				if(t[j]>t[i]){
					printf("%d\n",t[j]-t[i]-1);
				}
				else{
					printf("%d\n",t[i]-t[j]-1);
				}
			}			
		}
	}
	return 0;
}
2024/8/20 16:17
加载中...