_H1kar1 @ 2019-03-30 15:49:42
注释掉的是测试过程 数组开比正解还大,应该不是这个问题,,, re了2,9,10三个点
#include<iostream>
using namespace std;
int n,m;
int tr[10020]={0};
int findhead(int p){
//system("pause");
if(tr[p]==p) return p;//it's head itself
return tr[p]=findhead(tr[p]); //在这里压缩路径
}
/*
void unite(int a,int b){
//if(findhead(a)==findhead(b)) return ;//他们在一棵树上
tr[findhead(b)]=findhead(a);
}
*/
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)//reset
tr[i]=i;
int zi,xi,yi;
for(int i=1;i<=m;i++){
cin>>zi>>xi>>yi;
if(zi==1){
tr[findhead(xi)]=findhead(yi);
}
else
if(findhead(xi)==findhead(yi))
cout<<'Y'<<endl;
else cout<<'N'<<endl;
///////////////////////////////////////////////////
//cout<<"*****"<<endl;
//cout<<"findheadxi="<<findhead(xi)<<endl
// <<"findheadyi="<<findhead(yi)<<endl;
//for(int i=1;i<=m;i++)
// cout<<tr[i]<<' ';
//cout<<endl<<"*****"<<endl;
}
return 0;
}
谢谢指点了,真的难受
by Celestial_Scarlet @ 2019-03-30 15:54:13
@迪奥·布朗度 初始化炸了,是1~n
by Eason_AC @ 2019-03-30 15:54:42
for(int i=1;i<=m;i++)
tr[i]=i;
改成
for(int i=1;i<=n;i++)
tr[i]=i;
就可以了吧
by namespace_std @ 2019-03-30 15:55:12
m是2e5,n是1e4
然而你初始化的时候将1,...,m都初始化了啊
for(int i=1;i<=m;i++)//reset
^
by Hexarhy @ 2019-03-30 15:55:28
for(int i=1;i<=m;i++)//reset
tr[i]=i;
不太对,应该是i<=n
by Eason_AC @ 2019-03-30 15:55:39
楼上三个正解(逃
by _H1kar1 @ 2019-03-30 16:06:31
@HyyypRtf06 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)
by _H1kar1 @ 2019-03-30 16:06:37
@baoyu 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)
by _H1kar1 @ 2019-03-30 16:06:49
@Eason_AC 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)
by _H1kar1 @ 2019-03-30 16:07:07
@namespace_std 谢谢,终于A了,我第一次打并查集,一下午都在查并查集的基本操作上,哪能想到手滑打的初始化错了(汗)
by _H1kar1 @ 2019-03-30 16:07:39
突然想到我应该一次把人都at完的(扶额)