AcWing 836. 合并集合
原题链接
简单
作者:
千禧
,
2019-12-15 15:45:20
,
所有人可见
,
阅读 749
C++ 超时代码 求解决
#include <iostream>
using namespace std;
int n,m;
int bcj[10001];
int find(int x)
{
while(bcj[x] != x)
x = bcj[x];
return x;
}
void un(int x,int y)
{
int fx = find(x);
int fy = find(y);
if(fx!= fy)
bcj[fy] = fx;
}
int main()
{
cin >> n >> m;
for(int i=1 ;i <= n;i ++) bcj[i] = i;
int a,b;
char s;
while(m--)
{
cin >> s >> a >> b;
if(s == 'M')
{
un(a,b);
}
if(s == 'Q')
{
if(find(a) == find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
改成这样
return x == bcj[x] ? x : bcj[x] = find(bcj[x])
谢谢大佬!!!
Accepted 了
int find(int x) {
return x == bcj[x] : x ? bcj[x] = find(bcj[x]);
}改成这样就 OK了
find()函数中需要用到路径压缩,降低时间复杂度,另外,你的数组开的好像有点小,题中是 1e5