陌

用户名：lzy599

访问量：7249

签　名：

哪有什么签名

等　　级
排　　名	580
经　　验	4291
参赛次数	14
文章发表	12
年　　龄	0
在职情况	学生
学　　校	福建农林大学东方学院
专　　业

　　自我简介：

TA的其他文章

[传智杯]程序员节发橙子（C++代码）（简短+双指针+图示）
浏览：650

[传智杯]众数出现的次数-题解(C++代码)（简短+易懂）
浏览：359

蓝桥杯2019年第十届真题-完全二叉树的权值-题解(C++代码)（前缀和+简短 +图解）
浏览：949

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

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

　　作者: 陌　　　　发表时间：2020-04-16 21:42:03 浏览：2048　|　评论：9　

原题链接：蓝桥杯2019年第十届省赛真题-修改数组

## 声明
这个做法非原创，算是做个题解，做点笔记吧。
顺便分享一下这么优美的算法。

## 思路
**并查集结构说明**
每一个节点的值都是p[]用来表示节点。
当然一个节点可以作为根节点从而形成一棵树
那么如何将各个节点连接起来的呢？
就相当于链表，有一个指针，单向连接，这个指针就是对应节点的值，每一个节点都有一个值（指针）指向父节点。
![](/image_editor_upload/20200416092046_20903.png)
可以发现，p[]数组就是用来分配节点空间的，其里面男的值就是存储其父节点的地址。
父节点的父节点指向自身。这样就形成了一个集合，一棵树的结构。这个数据结构就叫并查集。
并查集的一般有两个操作，
1.就是判断两个节点是不是属于同一个集合（树）
2.将两个集合合并

借助的操作都是寻找祖宗节点：
1.如果两个节点的祖宗节点是同一个那么就是同一个集合
2.如果将两个集合的祖宗节点指向同一个，那么这两个集合就合并了

**本题思路**
根据题目给的思路：
首先我们每输入一个数，都会判断前面是否已经有过，如果有过就会+1，知道前面没有重复的数。
那么像不像并查集的指向呢，如果没有用过就是根节点，指向自己
如果已经用过了，就在自身的基础上+1，那么我们只要将其父节点指向比他大1的节点就可以了。
简单来说就是两个规则：如果没有用过，指向自身就是输出自身
如果用过，输出父节点，如果父节点还被用过就一直循环知道，找到祖宗节点（没被用过）
样例分析
![样例分析](/image_editor_upload/20200416094006_28526.png "样例分析")

再加上路径压缩，时间复杂度会达到将近o(1)的程度

## 代码：
```
#include<iostream>
using namespace std;
const int N = 1000010;
int p[N];

//查找祖宗节点+路径压缩
int find(int x )
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < N; i++)
        p[i] = i;
    for(int i = 0; i < n; i++)
    {
        int x;
        scanf("%d",&x);
        x = find(x);
        printf("%d ",x);
        p[x] = x+1;
    }
    return 0;
}
```
时间速度：
![AC](/image_editor_upload/20200416094400_31214.png "AC")

0.0分

42 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

manstain

逆天

2023-03-18 21:55:52

Passerby

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

陈锦强cjq

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

2021-03-25 21:19:47

wsnd

大佬牛逼，笨笨的我用散列超时飞天。

2021-03-25 20:25:23

学而进

这算法真的厉害，什么大佬想出来的，跪了跪了

2021-03-18 13:38:57

lee

哦哦原来这就是路径压缩啊

2021-01-23 16:46:12

lee

你这代码好像没有路径压缩啊

2021-01-23 16:29:06

陌

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

点我有惊喜！你懂得！

C二级辅导-同因查找（C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

钟神赛车（C++代码）

【密码】（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

用筛法求之N内的素数。（C语言代码）

【矩阵】（C++代码）

剪刀石头布（C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

陌

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

点我有惊喜！你懂得！

C二级辅导-同因查找 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

钟神赛车 （C++代码）

【密码】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

【矩阵】 （C++代码）

剪刀石头布 （C语言代码）

C语言程序设计教程（第三版）课后习题12.3 （C语言代码）

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

用筛法求之N内的素数。（C语言代码）

C二级辅导-同因查找（C语言代码）

　　评论区

钟神赛车（C++代码）

【密码】（C语言代码）

用筛法求之N内的素数。（C语言代码）

【矩阵】（C++代码）

剪刀石头布（C语言代码）