0.0分

39 人评分

  评论区

逆天
2023-03-18 21:55:52
如果使用unordered_map来替代数组来实现并查集的话,速度反而慢了。
#include <bits/stdc++.h>
using namespace std;
unordered_map<int,int> mp;
int find(int x){
	if(mp.count(x)) mp[x]=find(mp[x]);
	else{
		mp[x]=x+1;
		return x;
	}
	return mp[x];
}
int main(){
	int n;
	cin>>n;
	vector<int> arr(n);
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	for(int i=0;i<n;i++){
		if(!mp.count(arr[i])) mp[arr[i]]=arr[i]+1;
		else{
			arr[i]=find(arr[i]);
		}
	}
	for(int i=0;i<arr.size();i++) cout<<arr[i]<<" ";
	return 0;
}
2022-04-06 22:46:30
查找祖宗结点函数部分,为什么换成其他的书写方式就运行超时了呢?为什么这样的书写方式直接默认了路径压缩呢?(其他的都需要额外写一部分路径压缩的代码)
比如,改成如下这种形式就会提示超时,这又跟您的代码有什么区别呢?
int find(int x )
{
    while(x!=find(x))
    {
        x=find(x);
    }
    return x;
}
2021-04-05 21:13:05
为什么它包含iostream头文件还可以用scanf()和printf()
2021-03-25 21:19:47
大佬牛逼,笨笨的我用散列超时飞天。
2021-03-25 20:25:23
这算法真的厉害,什么大佬想出来的,跪了跪了
2021-03-18 13:38:57
哦哦原来这就是路径压缩啊
2021-01-23 16:46:12
你这代码好像没有路径压缩啊
2021-01-23 16:29:06