虽然过了,但仍不理解
查看原帖
虽然过了,但仍不理解
1025267
Space_2011楼主2024/12/26 13:49

11pts:

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int t,x,y,fa[N],dis[N],siz[N];//dis->½áµãµ½¸ù¾àÀë   siz->ËùÔÚ¼¯ºÏÓм¸¸öÔªËØ 
char c;
int get(int x){
	if(fa[x]==x) return x;
    dis[x]+=dis[fa[x]];
    fa[x]=get(fa[x]);
    siz[x]=siz[fa[x]];
    return fa[x];
}
void merge(int x,int y){
	int dx=get(x),dy=get(y);
    fa[dx]=dy;
    dis[dx]+=siz[dy];
	siz[dx]+=siz[dy];
    siz[dy]=siz[dx];
}
bool ck(int x,int y){
	int fx=get(x),fy=get(y);
	return fx==fy;
}
int main() {
	scanf("%d",&t);
	for(int i=0;i<=3e4;i++) fa[i]=i,dis[i]=0,siz[i]=1;
	for(int i=1;i<=t;i++){
		cin>>c>>x>>y;
		if(c=='M') merge(x,y);
		else{
			if(x==y) cout<<0<<endl;
			else if(ck(x,y)==false) cout<<-1<<endl;
			else cout<<abs(dis[x]-dis[y])-1<<endl;
		}
	}
	return 0;
}

100pts:

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int t,x,y,fa[N],dis[N],siz[N];//dis->½áµãµ½¸ù¾àÀë   siz->ËùÔÚ¼¯ºÏÓм¸¸öÔªËØ 
char c;
int get(int x){
	if(fa[x]==x) return x;
	int k=fa[x];
    fa[x]=get(fa[x]);
    dis[x]+=dis[k];
    siz[x]=siz[fa[x]];
    return fa[x];
}
void merge(int x,int y){
	int dx=get(x),dy=get(y);
    fa[dx]=dy;
    dis[dx]+=siz[dy];
	siz[dx]+=siz[dy];
    siz[dy]=siz[dx];
}
bool ck(int x,int y){
	int fx=get(x),fy=get(y);
	return fx==fy;
}
int main() {
	scanf("%d",&t);
	for(int i=0;i<=3e4;i++) fa[i]=i,dis[i]=0,siz[i]=1;
	for(int i=1;i<=t;i++){
		cin>>c>>x>>y;
		if(c=='M') merge(x,y);
		else{
			if(x==y) cout<<0<<endl;
			else if(ck(x,y)==false) cout<<-1<<endl;
			else cout<<abs(dis[x]-dis[y])-1<<endl;
		}
	}
	return 0;
}

我就改了get函数,两个get函数感觉没区别,为什么一个能过,一个不能?

调了好长时间qwq

2024/12/26 13:49
加载中...