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

2244 阅读 16 评论 0 点赞

原题链接：蓝桥杯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分

33 人评分

本文分类：题解列表
浏览次数：2244 次浏览
发布日期：2020-04-16 21:42:03
本文链接：https://blog.dotcpp.com/a/69517

上一篇 > [编程入门]数字逆序输出-题解(C语言代码) (使用堆栈方法)
下一篇 > [编程入门]数组插入处理-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 16 条评论

wsnd 3年前回复TA

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

学而进 3年前回复TA

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

-. 3年前回复TA

@lee find 函数在找到根后，返回了根节点，所有的节点就都指向了根节点。思想体现在这里： p[x] = find(p[x]); 而不是 find(p[x])。

lee 3年前回复TA

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

lee 3年前回复TA

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

随意凯 4年前回复TA

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

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 16 条评论

发表评论 取消回复

评论列表共有 16 条评论

发表评论取消回复