Judgelight @ 2023-04-09 09:11:26
启发式合并，但是去掉了启发式。
link
#include<bits/stdc++.h>
#define N 10009
using namespace std;
int n,m,belong[N];
vector<int>v[N];
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
v[i].push_back(i);
belong[i]=i;
}
for(int i=1;i<=m;i++){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
if(belong[x]==belong[y]){
continue;
}
x=belong[x],y=belong[y];
// if(v[x].size()>v[y].size()){
// swap(x,y);
// }
for(int j=0;j<v[x].size();j++){
belong[v[x][j]]=y;
v[y].push_back(v[x][j]);
}
v[x].clear();
}
else{
v[belong[x]]==v[belong[y]]?cout<<"Y"<<endl:cout<<"N"<<endl;
}
}
return 0;
}by _Haoomff_ @ 2023-04-09 09:18:22
@Judgelight 这是一道橙题……
不要质疑一道通过76.27k的题目
by Judgelight @ 2023-04-09 09:21:31
@Haoomff 但是我时间复杂度是错误的啊。
by Sprague_Garundy @ 2023-04-09 09:22:08
@Haoomff 不会回复可以不回复，人家说的是数据水不是数据错了。
by zym113 @ 2023-04-09 10:05:32
by undefind @ 2023-06-17 09:36:55
已AC，语言：C++14（GCC9）
#include<bits/stdc++.h>
using namespace std;
const int Nmax=1e6+7;
int fa[Nmax];
int find(int x){
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
void merge(int a,int b){
int r1=find(a),r2=find(b);
if(r1!=r2) fa[r1]=r2;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
while(m--){
int z,x,y;
cin>>z>>x>>y;
if(z==1) merge(x,y);
else{
if(find(x)==find(y)) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
return 0;
}by y_kx_b @ 2023-07-27 21:40:45
@zym113 不对啊，复杂度不是