Boar @ 2020-08-04 09:01:49
#include<bits/stdc++.h>
using namespace std;
struct Node{
unsigned short pre;
}a[10000];
int fnd(int p){
return a[p].pre==p?p:fnd(a[p].pre);
}
void crp(int p){
a[p].pre=fnd(p);
}
void mrg(int x,int y){
int xp=fnd(x);
a[xp].pre=y;
}
bool rlt(int x,int y){
return fnd(x)==fnd(y);
}
int main(){
unsigned short n;
int m;
for(int i=0;i<10000;i++) a[i].pre=i;
cin>>n>>m;
for(int z,x,y,i=0;i<m;i++){
cin>>z>>x>>y;
if(z==1) mrg(x,y);
else cout<<(rlt(x,y)?'Y':'N')<<endl;
}
return 0;
}
by liujiageng @ 2020-08-04 09:08:00
路径压缩呢
by Meowco @ 2020-08-04 09:32:55
void mrg(int x,int y){
int xp=fnd(x);
a[xp].pre=y;
}
这一步导致MLE
void mrg(int x, int y) {
int xp = fnd(x);
a[xp].pre = fnd(y);
}
int fnd(int p){
return a[p].pre==p?p:fnd(a[p].pre);
}
这一步会导致TLE
int fnd(int p) {
return a[p].pre == p ? p : a[p].pre = fnd(a[p].pre);
}
初始化
for(int i=0;i<10000;i++) a[i].pre=i;
→
for (int i = 1; i <= 10000; i++) a[i].pre = i;
by Boar @ 2020-08-04 10:39:28
@RBpencil 谢谢,已经过了