蓝桥杯2019年第十届真题-修改数组-题解(C++代码)（链表式并查集 + 这是什么神仙算法）

manstain 2年前 回复TA

逆天

Passerby 3年前 回复TA

如果使用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;
}

阿状 3年前 回复TA

@wsnd 我也是

陌 4年前 回复TA

@陈锦强cjq 这个是在别的网站的，他在后台自动加上 C 语言的标准输入输出了。如果出错也可以自己加上哈

陌 4年前 回复TA

@学而进 哈哈，推荐 Acwing 啊

11.2km/s 4年前 回复TA

@我叫不紧张 最后栈溢出

11.2km/s 4年前 回复TA

@我叫不紧张 宁这个不是死循环了，一直执行find(x）没有返回

我叫不紧张 4年前 回复TA

@我叫不紧张 懂了，不愧为大佬，两行代码就实现了这么多的功能。

我叫不紧张 4年前 回复TA

查找祖宗结点函数部分，为什么换成其他的书写方式就运行超时了呢？为什么这样的书写方式直接默认了路径压缩呢？（其他的都需要额外写一部分路径压缩的代码）
比如，改成如下这种形式就会提示超时，这又跟您的代码有什么区别呢？
int find(int x )
{
    while(x!=find(x))
    {
        x=find(x);
    }
    return x;
}

陈锦强cjq 4年前 回复TA

为什么它包含iostream头文件还可以用scanf（）和printf（）

发表评论 取消回复

登录/注册