陌

用户名：lzy599

访问量：7249

签　名：

哪有什么签名

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

蓝桥杯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编程助手吧

　　评论区

随意凯

这些题目怎么连数据范围也不告诉，非要我们自己试错？

2020-08-24 12:12:40

陌

TA的其他文章

你可能喜欢

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

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

IP判断（C语言代码）

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

模拟计算器（C语言代码）

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

评论区

精彩推荐

妹子杀手的故事（C语言代码）

C语言训练-求函数值（C语言代码）

成绩转换（C语言代码）

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

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

C语言训练-大、小写问题（C语言代码）

WU-复数求和（C++代码）

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

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

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

陌

TA的其他文章

你可能喜欢

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

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

IP判断 （C语言代码）

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

模拟计算器 （C语言代码）

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

评论区

精彩推荐

妹子杀手的故事 （C语言代码）

C语言训练-求函数值 （C语言代码）

成绩转换 （C语言代码）

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

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

C语言训练-大、小写问题 （C语言代码）

WU-复数求和 （C++代码）

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

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

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

IP判断（C语言代码）

模拟计算器（C语言代码）

　　评论区

妹子杀手的故事（C语言代码）

C语言训练-求函数值（C语言代码）

成绩转换（C语言代码）

C语言训练-大、小写问题（C语言代码）

WU-复数求和（C++代码）