搜索结果
查询Tags标签： 查集，共有 135条记录-
CSP-S2019 树上的数（并查集，dfs）
CSP-S2019 树上的数 \(n\) 树。\(n\) 排列卡片。\(i\) 卡片初始在 \(p_i\)。每次删一条边可以交换两端卡片。删光边最后卡片 \(i\) 位置 \(P_i\)。求字典序最小 \(P\)。 CODE 无可奉告。
2022/9/15 23:17:21 人评论 次浏览 -
并查集
声明：与学校集训内容无关。 并查集是一种树形结构，基本的应用就是判断两个元素是否在同一个集合内，也可以将两个元素所在的集合合并。 举个奇怪的例子。 原理&代码实现+优化 假设这里有一些P主，他们有不同的口味（派别），有摇滚，重金属，古典等等等。 现在我们假…
2022/9/14 23:17:13 人评论 次浏览 -
并查集
并查集，是用代表元素来维护一个集合的数据结构。可以差不多\(O(1)\)地查询两个元素是否在同一个集合内。 并查集主要通过路径压缩和按秩合并减小复杂度。单独用的话最坏复杂度都是\(O(logn)\)的（虽然只路径压缩的均摊复杂度还是差不多\(O(1)\)）。分开讲。 首先是初始化…
2022/9/3 23:22:58 人评论 次浏览 -
题解：【WC2005】双面棋盘
【WC2005】双面棋盘 题目链接 这天做双面棋盘这道题，发现题解里面大多都是 LCT ，对于线段树套并查集的写法思路讲评很少而且不大清晰，因此有了这一篇题解。 维护联通块的数量，很容易联想到使用并查集，考虑暴力，用并查集记录每个点的连通性，最后统计块数即可。但是如…
2022/8/24 23:26:35 人评论 次浏览 -
并查集学习笔记
很抱歉这篇博客晚来了(该放在Kruskal前面的)...... 并查集，故名思意，就是用来高效进行合并、查询集合的数据结构，为了方便，我们可以把每一个结点看成树形结构即可。 1.查询 Q1：我们该如何查询某一个结点在哪一个集合呢？ A1：我们知道如果需要区分开所有集合，就应该…
2022/8/11 6:25:47 人评论 次浏览 -
ZZULI (2022河南萌新联赛 四)
题目描述分析 读题不认真这个毛病什么时候能改? 我竟然看成最长上升子序列问题了, 而且还把代码写好.......(其实就算看出来是并查集, 我也不会写qwq)赛后借鉴大佬代码, 收获很大 以后看到连通块这个词, 就往并查集的方向想 AC代码 #include <iostream> #include &…
2022/7/31 23:43:50 人评论 次浏览 -
并查集(集合合并,路径压缩优化)
并查集(路径压缩优化) 摘自acwing算法模板 并查集 并查集的作用： 1.两个集合合并 2.询问两个集合是否在同一个集合中怎么实现路径压缩？ 如果x不是祖宗结点，就让父亲结点 = 祖宗结点 ， 最后返回父亲结点 怎么实现集合合并 让a祖宗的结点的父亲等于b结点的结点 代码 #in…
2022/7/31 6:22:48 人评论 次浏览 -
luogu P5064 [Ynoi2014] 等这场战争结束之后
题面传送门 按秩合并并查集写错复杂度假掉以为自己被卡常卡了好久。 首先这种撤销题看上去就是把操作树建立出来然后dfs变成加入与撤销。 然后我们考虑对值域分块，这样看上去求\(k\)小值会可做一些。 首先我们需要确定每个询问在哪个块，这并不困难。我们考虑在dfs时用并…
2022/7/9 23:51:38 人评论 次浏览 -
2022.7.8 并查集+路径压缩
一个简洁优秀的讲解https://zhuanlan.zhihu.com/p/93647900 【模板】并查集 题目描述 如题，现在有一个并查集，你需要完成合并和查询操作。 输入格式 第一行包含两个整数 \(N,M\) ,表示共有 \(N\) 个元素和 \(M\) 个操作。 接下来 \(M\) 行，每行包含三个整数 \(Z_i,X_i,…
2022/7/8 23:55:22 人评论 次浏览 -
2022暑假集训队选拔赛补题
E ginger的染色 首先对于一个排列 ，如果看成环图的结构，那么 就向 连一条无向边。所以对于任意一个排列就会产生若干个环，连通性可以用并查集维护，现在对每个点进行黑白染色，题意转换为对于环中任意相邻两点颜色不能相同，那么只有偶数元环才能够染色成二分图，而每个…
2022/6/21 23:24:33 人评论 次浏览 -
「算法学习」并查集以及它的一些扩展
并查集 简介 并查集是一种树形的数据结构，它支持两种操作：查找（find）：查询某个元素属于哪个集合； 合并（merge）：将两个集合合并成同一个集合。查找 我们令 find 函数表示寻找 \(x\) 的祖先。如果 \(x\) 已经是祖先，则返回；否则递归到 \(f[x]\) 的子问题。 int f…
2022/6/8 1:20:09 人评论 次浏览 -
使用并查集解决的相关问题
作者: Grey 原文地址：使用并查集解决的相关问题 关于并查集的说明，见如下博客： 使用并查集处理集合的合并和查询问题 相关题目 LeetCode 200. 岛屿数量 本题的解题思路参考博客 使用DFS和并查集方法解决岛问题 LeetCode 547. 省份数量 主要思路 横纵坐标表示的是城市，…
2022/6/4 23:50:07 人评论 次浏览 -
778. 水位上升的泳池中游泳(并查集)
778. 水位上升的泳池中游泳在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。 当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定…
2022/5/5 6:16:25 人评论 次浏览 -
1202. 交换字符串中的元素(并查集)
1202. 交换字符串中的元素给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。 你可以 任意多次交换 在 pairs 中任意一对索引处的字符。 返回在经过若干次交换后，s 可以变成的按字典序最小…
2022/5/5 6:13:13 人评论 次浏览 -
947. 移除最多的同行或同列石头(并查集)
947. 移除最多的同行或同列石头n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。 如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。 给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头…
2022/5/5 6:12:51 人评论 次浏览
