并查集3
课题1 并查集
研究时间：6.30~7.4
参考书目：
《算法艺术和信息学竞赛》——By 刘汝佳，黄亮
《数据结构（C语言版）》——By 严蔚敏，吴伟民
《算法与数据结构》——By 傅清祥，王晓东
《算法I—IV（C实现）》——By [美]Robert Sedgewick
【关键字】
并查集联系问题并查算法等价关系和等价类树和数组启发式快速合并优化压缩路径
【绪论】
在讲述并查集之前，我们来看一个很简单的问题：
一个简单题：联系问题
我们用实数对（p，q）表示p、q是相联系的。同样，实数对(p,r) 代表p 和r 是相联系的。如果存在两个实数对（p,q）、（p,r），那么我们说，p,q,r 都是相联系的，即：具有传递性。我们的任务就是些程序来判断两个数是不是相联系的。
比如
有如下几个实数对（ 1 ， 2 ）（ 2 ， 3 ）（ 3 ， 4 ）（ 4 ， 5 ）（ 1 ， 6 ）（ 2 ，8 ）
我们需要问的是：2 6 是不是相联系的。
——我们由题意可以很快得知：他们是相联系的。
(1 2 相联系，1 6 相联系，2 6 显然相联系！)
分析
上面所说的问题实际上可以看成一个集合问题，将它数学化一点，就是(p ，q) 就表示p ，q 在同样一个集合中，而最终我们要判断x ， y 是不是在一个集合里面。很显然，题目不会告诉我们一个集合有多少个元素，分别是什么，他只会一次又一次地提示我们两个元素属于一个集合，而这个集合，就是我们所需要去构造的。然后，我们可以直接判断所询问的数x ， y 在不在一个集合中。
拓展：
这类问题在现实中有着较为广泛应用及拓展：
1、大型电网中，每次告诉我们两个点相联接，最后问x ， y 是不是相联接
2、亲戚问题：每次告诉你某两个人之间存在亲戚关系，最后问：x ， y 是否是亲戚
从上面的例子中我们不难发现，在解决某些问题的时候，我们需要构造出一系列庞大的关系网络，而怎样才能很好的解决这些问题，我们现在要讨论的是一种算法——并查算法（Union-Find Algorithms ），对应于它的抽象数据类型叫做——并查集
【数学基础】
首先，我们从数学的角度给出等价关系和等价类的定义：
定义：如果集合S 中的关系R 是自反的，对称的，传递的，则称他为一个等价关系——自反 x=x
——对称若 x=y 则 y=x
——传递若 x=y y=z 则 x=z
要求：x 、 y 、z 必须要同一个子集中
定义：如果R 是集合S 的等价关系。对于任何x∈S，由[x]R={y|y∈S and xRy}给出的
集合[x]R S
称为由x∈S生成的一个R 的等价类。
定义：若 R 是集合S 上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以按R 将S 划分为若干不相交的子集S1，S2，S3，S4 ……他们的并即为S ，则这些子集S i变称为S 的R 等价类
划分等价类的问题的提法是：要求对S 作出符合某些等价性条件的等价类的划分，已知集合S 及一系列的形如“ x 等价于y ”的具体条件，要求给出S 的等价类的划分，符合所列等价性的条件。< 我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S 划分成n 个联系的子集，然后再判断x ， y 是否在一个联系子集中>
【并查算法】
我们仍然从绪论中的联系问题来入手。
开发一种高效算法来解决问题的第一步用一种简单的方法来解决问题。如果我们需要解决一些简单的特殊的具体情况，那么简单的程序就能够帮我们工作。但是若要做出一种高效算法，那简单的算法可以为我们提供一些一定范围内数据来验证我们的算法正确性。我们开发程序虽然要考虑效率，但是最基础而又最重要的是要确保解决问题正确性。
所以，我们首先想到的解决问题的方法是：储存所有输入的实数对，然后，写一个函数来，通过它来求出要求的实数对是否相联系。那么我们必须考虑以下几个问题：第一，如果数据很大，我们有没有那么多空间来储存这些实数对？第二，即使我们把所有的数据都储存了下来，我们也没有办法马上报出答案！< 那储存所有数据就是费力不讨好的工作了> 算法I
program algorithm1
begin
readln(n);
for i:=1 to n do id[i]:=I;
while not eof do
begin
readln(p,q)
if id[p]=id[q] then
else begin
t:=id[q];
for i:=1 to n do
if id[i]=t then id[i]:=id[p]
end;
end;
end.
我们来讨论上面这种名为快速查找(quick find) 的算法。
我们用数组的下标来表示集合名，并规定，一开始第i 的集合包含集合i 。如果p 和q 是相联系的，当且仅当p 号元素和q 号元素他们的数据值（即表示他们所在的集合）相等。为了表现出对p 和q 进行并操作，我们扫描整个数组，改变所有数据值和 p 相同的，变为q 。当然这种选择是任意的，我们也可以把数据值和q 相同的，变为 p 。这个操作如果要进行查找，那么就是直接查找就可以了。
性质：快速查找的算法至少执行M*N 次命令来解决一个有n 个事物和m 次和并操作的联系问题
小结：现代计算机每秒执行一亿到十亿次命令，所以当M 和N 很小的时候，我们不会察觉到算法的优劣。但是我们同样可以找到几百万个事物，几十亿次合并的命令，所以这样的
算法就很难承受了。
算法II
我们接下来考虑的是另一种叫做快速合并(quick-union) 算法。我们设定每一个事物指向同一个集合里面的另一个事物，并且是一个无环的结构。决定两个事物是不是在同一个集合，我们移动每一个的指针一直指向他们的根，两个事物在同一个集合里面，当且仅当我们的根相等。如果他们不在同一个集合里面，我们将停在不同的事物上面。对于并操作，我们只需要将一个的父亲连接到另一个的根的下面。这就是为什么这种算法成为快速合并(quick-union) 算法的原因！这种算法明显优于第一种算法，为什么？因为它没有反复地对数组进行扫描，确切地说，它不需要反复扫描。
性质：对于M>N ，快速合并算法将执行超过M*N/2 次命令来解决由M 对N 个事物的联系问题
program algorithm2
begin
i:=p;
while i<>id[i] do i:=id[i];
j:=q;
while j<>id[j] do j:=id[j];
if i=j then
else id[i]=j
end;
{ 上面的两个循环语句就是为了找到i 和j 所在的集合的根，然后在合并}
小结：这种方法有一个很大的缺陷，我们来讨论一下：如果输入数据是1~2 ，2~3 ， 3~4 那么在n-1 次输入后，我们就有了n 个事物在集合中，那么它的图像（一棵树）就会将近成为一条直线。那么，在执行查找操作的时候，对于查找n ，我们需要移动n-1 次指针，因此，平均的移动指针数量是：
（0+1+2+ …… +(n-1) ）/n=(n-1)/2 。
如果我们所有的情况都是这样的，很显然，m 对N 个事物的联系，将会大于M*N/2 次操作。
优化I
上面这种算法虽然较为优秀，但是我们也看到了其在最坏情况下的复杂度，显然这种算法我们依然难以接受。不过幸运地，我们有一种修正的方法来解决这个问题，即第一种对于并查集的优化，算法的思想在于把深度小的树合并到深度大的树中间去，以至于平衡整个结果的深度，这样的话，我们将避免出现上述的bad case 。当然，我们需要的是多一些的代码，和另外一个数组，用来记录深度。这样将把程序的效率大大地提高。我们称为启发式快速合并（weighted quick-union ）算法。
这种启发式快速合并的算法，我们发现即使在平常情况下都比，集合树都比不优化的情况下，深度小。我们用图形的方式为大家展示一下他们的区别。
那么，这样的话我们发现，如果有2n个节点，我们只需要将指针移动n次就可以找到我们需要的事物，这就大大提高了效率。
性质：启发式快速合并算法最多移动2logN次指针就可以决定两个事物是否想联系。
我们可以证明，在一个有k个元素的集合，我们将保证移动不超过logk次就可以找到目标。
证明：我们合并一个有i个结点的集合和一个有j个结点的集合，我们设i<=j，我们在一个小的集合中增加一个被跟随的指针，但是他们现在在一个数量为i+j的集合中。由于
<=
+
1+
=
+，所以我们可以保证性质。
)i
i(
)j
logi
log
i(
log
< Prove: When we combine a set of i nodes with a set of j nodes with i<=j, we
increase the number of pointers that must be followed in the smaller set by 1, but they are now in a set of size i+j, so the property is preserved because
)j i (log )i i (log logi 1+<=+=+.>
性质：启发式快速合并所得到的集合树，其深度不超过??1log n 2+，其中n 是集合S 中的所有子集所含的成员数的总和
证明：我们可以用归纳法证明：
当i=1时，树中只有一个根节点，即深度为1，又??111log 2=+，所以正确 假设i<=n-1时成立，尝试证明i=n 时成立。不是一般性，可以假设此树是由含有m （1<=m<=n/2）个元素，根为j 的树Sj ，和含有n-m 个元素、根为k 的树Sk 合并而得到， 并且，树j 合并到树k ，根是k 。
若合并前子树Sj 的深度<子树Sk 的深度，则合并后的树深度和Sk 相同，深度不超过??1)m n (log 2+-，显然不超过??1log n 2+。
若合并前的子树Sj 的深度>=子树Sk 的深度，则合并后的树的深度为Sj 的深度+1，即??????1log 1)2m (log 1)1log (n m 222+<=+=++。
program algorithms3 begin
for i:=1 to n do begin id[i]:=i; sz[i]:=1; end; while not eof do begin i:=p;
while i<>id[i] do i:=id[i]; j:=q;
while j<>id[j] do j:=id[j]; if i=j then
else if sz[i] begin id[i]:=j;sz[j]:=sz[j]+sz[i];end else begin id[j]:=I;sz[i]:=sz[i]+sz[j];end; end; end. 小结：实践告诉我们上面所陈述的性质对于一个m 条边n 个事物的联系问题，最多执行MlogN 次指令。我们只是增加了一点点额外的代码，我们就把程序的效率很大地提升了。大量的实验可以告诉我们，启发式合并可以在线形时间内解答问题。更确切地说，这个算法运行时间的花费，很难再有更加明显的优秀、高效的算法了。 当然，我们可以再加一点优化，来确保这整个操作保证在线性范围内，来使整个算法再优化那么一点。 优化II 这个优化叫做压缩路径（compresses paths）。一种简单的方法，就是在添加另一个集合的时候，把所有遇到的结点都指向根节点。这种方法叫做满路径压缩(full compresses paths)，而且这是一种很常用的方法。 当然，压缩路径可以有很多种方法，另外一种压缩路径的方法就是通过二分压缩路径（compresses paths by halving），具体思想就是把当前的结点，跳过一个指向父亲的父亲，从而使整个路径减半深度减半。这种办法比满路径压缩要快那么一点点。数据越大，当然区别就会越明显。 优化II的两种方法，本质都是为了将路径深度更加地减小，从而使访问的时候速度增快，是一种很不错的优化。 只要把一下的代码替换掉上面的第一个优化的循环就可以达到目的（下面的代码是by halv ing的方法） I:=p; While i<>id[i] do Begin Id[i]:=id[id[i]]; I:=id[i]; End; J:=q; While j<>id[j] do Begin Id[j]:=id[id[j]]; J:=id[j]; End; 【复杂度】 并查集进行n次查找的时间复杂度是O(nα(n))，其中α(n)是一个增长极其缓慢的函数，它是阿克曼函数(Ackermann Function)的某个反函数。它可以看作是小于5的。所以综上可以认为并查集的时间复杂度是线性的。 【算法比较】 以下表格是对于以上的各种算法的时间考察，摘录自《算法I—IV（C实现）》 N：顶点数 M：联系数 F：快速查找算法（算法一） U：快速合并算法（算法二） W：启发式（优化一） P：满压缩路径（优化二，方法一）H：二分压缩路径（优化二，方法二）上图中，对应算法的数字是时间 习题 增加ing… 这个训练计划我也只是把我知道的知识点罗列出来而已. 其实acm还有很多方面的知识。 可能到acm生涯结束的时候还是无法把所有的知识都吃透 所以acm的知识能学多少算多少，知识重要的不是你知道的多，重要的是你能否熟练的运用他们！ 题目注意事项： zoj：https://www.wendangku.net/doc/e65918226.html,/ grid：https://www.wendangku.net/doc/e65918226.html,/ hdu：https://www.wendangku.net/doc/e65918226.html,/ zquoj：也就是我们的oj 一．数据机构基础。 请自学完数据结构书：2，3，4，6，7，9.1，9.2.1 9.3 10 这几章，带*号可以暂时掠过，以后再看。然后自行完成oj DS开头的题目。 注意栈队列这些数据结构一般不用像书本那样写得那么严谨。在acm中，往往因为时间关系，一般写成简单的模式：请参考附件：栈与队列acm中的简单实现.txt 其它数据结构请自行简化。 二．其他数据结构 1.trie树 请看附件trie树的相关附件或到网上搜索。注意自己写好和简化模版。 Trie树最好使用静态分配实现！ poj 3630 hdu 1251 2.并查集 Hdu：1558 1811 1829 1198 3.图论专题： 简单的说下图怎么存储。 图通常分为邻接表和邻接矩阵两种方式储存。 请先移步到数据结构书祥看这两种实现方式。 邻接表：我们知道要动态分配内存。这种方式有时会导致效率低下。我们可以模拟一下动态分配内存，详见附件静态分配。 这部分图论可参考 https://www.wendangku.net/doc/e65918226.html,/p-251720691.html 部分题目.这本书有讲解。 1.图的基本概念 poj：1659 2.图的遍历和活动问题 zoj：2110 1709 1649 2913 1060 2193 2412 1008 2165 1136 1361 1091 1083 poj：2935 1270 3687 信息学奥赛中的特殊数据结构——并查集 在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。 一、数学准备 首先，我们从数学的角度给出等价关系和等价类的定义： 定义1：如果集合S中的关系R是自反的，对称的，传递的，则称他为一个等价关系。 ——自反：x＝x； ——对称：若x＝y，则y＝x； ——传递：若x＝y、y＝z，则x＝z。 要求：x、y、z必须要同一个子集中。 定义2：如果R是集合S的等价关系。对于任何x∈S，由[x]R＝{y|y∈S and xRy}给出的集合[x]R S 称为由x∈S生成的一个R的等价类。 定义3：若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划 分。即可以按R将S划分为若干不相交的子集S 1，S 2 ，S 3 ，S 4 ，……，他们的并即为S，则这 些子集S i 变称为S的R等价类。 划分等价类的问题的提法是：要求对S作出符合某些等价性条件的等价类的划分，已知集合S及一系列的形如“x等价于y”的具体条件，要求给出S的等价类的划分，符合所列等价性的条件。（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S划分成n个联系的子集，然后再判断x，y是否在一个联系子集中。） 二、引题——亲戚（relation） 【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。（人数≤5000，亲戚关系≤5000，询问亲戚关系次数≤5000）。 【算法分析】 1. 算法1，构造图论模型。 第一章：绪论 1．数据结构的基本概念和术语 ?数据、数据元素、数据项、数据对象、数据结构等基本概念 ?数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系 ?数据结构的四种逻辑结构及四种常用的存储表示方法 2．算法的描述和分析。 ?无穷大阶的几种描述方法的区别 ?算法特征及其评价标准 ?算法的时间复杂度和空间复杂度的概念 ?几种常见复杂度的好坏程度 ?就（原）地算法的含义 ?算法描述和算法分析的方法 1. 设n是偶数，试计算运行下列程序段后m的值，并给出该程序段的时间复杂度。 m=0; for (i=1; i<=n; i++) for (j=2*i; j<=n; j++) m=m+1; 2. 下列算法对一n位二进制数加1，假如无溢出，该算法在最坏情况下时间复杂度是什么？并分析它的平均时间复杂度。 void func (int A[n]) //A[n]中每个元素取值0或1 {inti = n; while (A[i] == 1) { A[i] = 0； i-} A[i]=1；} 3. 调用下列函数f(n) 回答下列问题: （1）试给出f(n)值的大小，并写出f(n) 值的推导过程; （2）假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。 int f(int n) {inti, j，k, sum= 0; for(i=1; i 数据结构与算法 课程设计报告 课程设计题目：并查集检查网络 专业班级：信息与计算科学1001班 姓名：学号： 设计室号： 设计时间： 2011-12-29 批阅时间：指导教师：成绩： 《数据结构与算法》课程设计报告 (2) 一、课题：并查集检查网络 (3) 1.题目要求： (3) 2.输入要求： (3) 3.输出要求： (3) 二、并查集操作 (4) 1.Creat() (4) 2.find（int e） (4) 3.hebin(int A ,int B) (4) 三、并查集的优化 (5) 1．路径压缩 (5) 2.启发式合并 (6) 四．问题实现 (6) 五．数据显示： (10) 《数据结构与算法》课程设计报告 姓名： 学号： 专业： 一、课题：并查集检查网络 1.题目要求： 给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。 请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输。 2.输入要求： 输入若干测试数据组成。 对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。 接下来的几行输入格式为I C1 C2或者C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。 3.输出要求： 对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔 第一章数据结构基本概念 1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。 2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象= 对象+ 类+ 继承+ 通信。 要点： ·抽象数据类型的封装性 ·面向对象系统结构的稳定性 ·面向对象方法着眼点在于应用问题所涉及的对象 3、数据结构的抽象层次：理解用对象类表示的各种数据结构 4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。 要点：·算法与程序的不同之处需要从算法的特性来解释 ·算法的正确性是最主要的要求 ·算法的可读性是必须考虑的 ·程序的程序步数的计算与算法的事前估计 ·程序的时间代价是指算法的渐进时间复杂性度量 第二章数组 1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储 要点： ·数组元素的存放地址计算 2、顺序表：顺序表的定义、搜索、插入与删除 要点： ·顺序表搜索算法、平均比较次数的计算 ·插入与删除算法、平均移动次数的计算 3、多项式：多项式的定义 4、字符串：字符串的定义及其操作的实现 要点： ·串重载操作的定义与实现 第三章链接表 1、单链表：单链表定义、相应操作的实现、单链表的游标类。 要点： ·单链表的两种定义方式（复合方式与嵌套方式） ·单链表的搜索算法与插入、删除算法 ·单链表的递归与迭代算法 2、循环链表：单链表与循环链表的异同 3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点 4、多项式的链接表示 第四章栈与队列 1、栈：栈的特性、栈的基本运算 要点： ·栈的数组实现、栈的链表实现 ·栈满及栈空条件、抽象数据类型中的先决条件与后置条件 2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示 3、队列：队列的特性、队列的基本运算 要点： ·队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件·队列的链表实现：链式队列中的队头与队尾指针的表示、 4、双向队列：双向队列的插入与删除算法 5、优先级队列：优先级队列的插入与删除算法 第五章递归与广义表 1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解 要点：·链表是递归的数据结构，可用递归过程求解有关链表的问题 2、递归实现时栈的应用 要点：·递归的分层（树形）表示：递归树 高级数据结构设计－－并查集及实现学习笔记（有趣篇） 并查集的程序设计： 为了解释并查集的原理，我将举一个更有趣的例子。 话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”…… 两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。 但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。 下面我们来看并查集的实现。 int pre[1000]; 这个数组，记录了每个大侠的上级是谁。大侠们从1或者0开始编号（依据题意而定），pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的，比如欧阳锋，那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁？不认识！要想知道自己的掌门是谁，只能一级级查上去。find这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。 转载自South_wind的专栏 常见的数据结构运用总结 考虑到Obsidian三个成员的擅长领域，这段时间都在做杂题，算是学习各种算法吧，趁现在休息的时间，而且大家马上要备战今年的比赛了，写写自己专攻方面的一些心得吧 扯开线段树、平衡树这些中高级的东西，先说说基础的数据结构 栈 算是代码量最小的数据结构？出栈进栈都只有一句话而已 常见用途： 消去一个序列中的相同元素(做法大家应该都知道了吧，见过很多次了) 维护一个单调的序列(所谓的单调栈，dp的决策单调？) 表达式求值(经典的栈运用，如果使用的很熟悉的话，可以处理一元、二元运算，不过最近没见过类似的题目了) 用于辅助其他算法(计算几何中的求凸包) 队列 队列应该还是很常见的数据结构了，如果专攻图论的话，spfa应该是写烂了的 这里说到的队列，是狭义的普通的队列和循环队列，不包括后面讲的一些变形 注意循环队列的写法，尽量不要使用取模运算，不然的话，遇到不厚道的出题者，可以把取模的循环队列卡到死 常见用途： 主要用于辅助其他算法，比如说spfa，bfs等(建议习惯用stl的孩子手写queue，毕竟就几行代码而已，偷懒会付出代价的。。。) 双端队列 如果写dp写的多的话，这个东西应该还是算是比较基础的东西了，双端队列多用于维护一个满足单调性的队列 还是建议手写，stl的deque使用块状链表写的，那东西的复杂度是O(Nsqrt(N))的，不要被迷惑了。 常见用途： dp的单调性优化，包括单调队列优化和斜率优化，都要用到这个结构 计算几何中的算法优化，比如半平面交 树的分治问题中利用单调队列减少转移复杂度 链表Dancing Links 写图论的不要告诉我不会写这货，链表可以写单双向，循环非循环的，高级点儿的可以考虑十字链表，麻花链表 不过链表可以说是树形结构的基础，如果这个掌握的不好，那么树形结构写起来就会很纠结 链表的优势在于可以O(1)的插入删除，如果要求插入的位置只是在序列的两端的话，这个数据结构是最方便的了(无视双端队列) hash表就是用链表实现的，熟悉hash的同学可以试试看怎么使你的hash效率提高 并查集。 1、概念： 如果：给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。并查集是一种树型的数据结构，它是一个集合，这个集合的元素也是集合，常常在使用中以森林来表示。 2、并查集的主要操作： ①合并两个不相交集合 ②判断两个元素是否属于同一集合 初步分析觉得本题是一个图论中判断两个点是否在同一个连通子图中的问题。 1、识别水果模9第1题 在海上漂泊了249天后，由于食物和水都已消耗光了，三人已是筋疲力尽。终于，在第250天的早晨，一个隐隐约约的黑点在远处出现了，是一个小岛，三大护法高兴的几乎要跳起来。于是下令舰队全速前进，驶向小岛。 在登陆后，他们才知道，这就是著名的移花岛，岛上有三位女神：dp女神、涓涓女神和紫晶女神。由于三大女神与holy_one的关系不错，因此高兴地接待了他们三人。由于看到三人饥渴难耐，负责岛上水果的涓涓女神便带他们去了果园。 果园里水果丰富，共有n个，它们的标号为1~n，但有些水果是有毒，而且水果与水果之间有藤蔓相连，如果一个水果有毒，那么所有与它相连的所有水果都是有毒的。其中m 个水果上面会贴着一个标签，从标签上可以看出这个水果是否有毒。当然，如果这个水果的标签显示无毒，但它与有毒的水果相连，那它也是有毒的。 为帮助三人尽快吃到水果，涓涓女神给了他们一张毒物字典，只有通过字典上的对应关系翻译后，才能知道水果是否有毒。转化后的名称中包含'poison'，即表示这个水果有毒。输入： 第一行，字符串a 第二行，字符串b a串和b串长度都是26，a[i]到b[i]表示两个字母的对应关系。注意，对应关系是单向的。两个整数n和m。 以下m行， 每行第一个数是水果的标号k，后面是第k个水果的标签s k和s之间有空格分隔开 一个整数p。 以下p行，每行两个整数x,y表示第x个水果和第y个水果之间有藤蔓相连 输出： 无毒的水果的个数s:array[‘a’..’z’] of char; 样例输入： abcdefghijklmnopqrstuvwxyz s1 s[s1[i]]:=s2[i] abcdefghijklmnopqrstuvwxyz s2 3 2 1 poison x[i]:=x[i] or x[j] 2 viking 1 1 3 1 4 北京师范大学《数据结构》课程教学大纲一、课程基本信息 中文名称： 数据结构 英文名称：Data Structure 课程类别（公共任选课、学科基础课、专业方向课）：学科基础课 学分： 4学时： 48+32 建议开设学期：2 开课单位建议：信息科学与技术学院 主讲教师： （姓名） 沈复兴（性别） 男 （职称） （学科方向） 教授 计算机软件 郑新 女 副教授 计算机应用 肖永康 男 讲师 计算机应用 二、课程目标： 本课程的主要目标是使学生深入了解数据结构的思想和数据结构的实现方法，特别是数据结构在实际工作中的应用和技术。本课程追求理论联系实际，实践教学与相应的教学内容相呼应。在形式上，灵活多样地采取了实践、拓展性学习、报告会等多种形式，目的在于加深学生对所学内容的理解，发展学生从事发展算法与程序设计研究和实践的能力，努力做到学以致用，同时激发学生的学习兴趣和主动参与精神，更好地掌握和运用所学习的知识。 三、课程内容与主要学习材料（含教材及参考书目） 课程内容： 第一章 绪论 1. 教学内容: ?数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构、算法等。 ?抽象数据类型。 ?描述算法的程序语言（C++）。 ?算法时间复杂度和空间复杂度的分析。 2. 教学目的及要求 ?掌握数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系等数据结构的基本概念； ?了解数据类型、抽象数据类型、数据抽象和信息隐蔽原则以及面向对象这种数据抽象实现方法 ?了解算法的定义、算法的特性、算法的时间代价、算法的空间代价 ?掌握用C++语言描述算法的方法，能够使用C++语言编写程序 3. 教学重点 数据结构的概念；算法分析；C++语言。 4. 学时分配 本章共教授4学时. 第二章数组 1. 教学内容 ?线性表的基本概念 ?顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除； 使用顺序表的事例；顺序表复杂度分析 ?特殊矩阵的压缩存储：特殊矩阵定义、稀疏矩阵类定义、矩阵转置与快速转置、矩阵乘法与输出 ?字符串：字符串类型定义；字符串操作的实现；字符串的模式匹配 2. 教学目的及要求 ?了解线性表的逻辑结构特性，以及线性表的两种存储实现方式 ?熟练掌握顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算，掌握应用顺序表作为集合的简单操作 ?了解稀疏矩阵的定义及其数组实现 ?掌握字符串的定义及实现 3. 教学重点 线性表的基本概念、顺序表的实现及应用 4. 教学难点 矩阵的快速转置及模式匹配改进 5. 教学时间分配 本章共教授4学时. 第三章链表 1．教学内容 ?单链表：单链表的结构；单链表的类定义；单链表中的查找、插入与删除；带表头结点的单链表；单链表的游标类及静态链表 ?循环链表：循环链表的类定义及操作；用循环链表解约瑟夫问题； ?多项式及其相加：多项式的链表表示类定义；多项式的加法 ?双向链表：双向链表的类定义及操作 ?稀疏矩阵：稀疏矩阵的正交链表表示法及建立和删除操作 2．教学目的及要求 ?了解链表与数组一样，是一种实现级结构。有动态链表和静态链表之分 ?了解链表有单链表、循环单链表、双向链表之分 ?了解单链表的结构、特点 ?熟练掌握单链表的类定义、构造函数、单链表的查找、插入与删除算法 树结构的并查集 采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同，每个顶点纪录的不是它的子结点，而是将它的父结点记录下来。下面是树结构的并查集的两种运算方式 ⑴直接在树中查询 ⑵边查询边“路径压缩” 对应与前面的链式存储结构，树状结构的优势非常明显：编程复杂度低；时间效率高。 直接在树中查询 集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要O（1）时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为O（logN）。但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为O（N）。 边查询边“路径压缩 其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数——α（x）。对于可以想象到的n，α（n）都是在5之内的。 并查集：(union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M Alpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内（人类目前观测到的宇宙范围估算有10的80次方个原子，这小于前面所说的范围）这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是线性的。它支持以下三中种操作: －Union (Root1, Root2) //并操作；把子集合Root2并入集合Root1中.要求：Root1和Root2互不相交,否则不执行操作. －Find (x) //搜索操作；搜索单元素x所在的集合,并返回该集合的名字. －UFSets (s) //构造函数。将并查集中s个元素初始化为s个只有一个单元素的子集合. －对于并查集来说，每个集合用一棵树表示。 poj2513_欧拉通路+并查集 +hash/trie 收藏 这找了很多解题报告，都是用trie做的，有一些还干脆否定了hash，本人偏偏不信这个邪，用hash做。。。 hash代码： view plaincopy to clipboardprint? 1.#include 前十个是来自圣经的十大算法： 发起人的描述：《来自圣经的证明》收集了数十个简洁而优雅的数学证明，迅速赢得了大批数学爱好者的追捧。如果还有一本《来自圣经的算法》，哪些算法会列入其中呢？ 第一名：Union-find 严格地说，并查集是一种数据结构，它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构，使得编程复杂度降低到了令人难以置信的地步；用上一些递归技巧后，各种操作几乎都能用两行代码搞定。而路径压缩的好主意，更是整个数据结构的画龙点睛之笔。并查集的效率极高，单次操作的时间复杂度几乎可以看作是常数级别；但由于数据结构的实际行为难以预测，精确的时间复杂度分析需要用到不少高深的技巧。 第二名：Knuth-Morris-Pratt字符串匹配算法 关于此算法的介绍，请参考此文：六、教你从头到尾彻底理解KMP算法。KMP算法曾经落选于二十世纪最伟大的十大算法，但人们显然不能接受，如此漂亮、高效的KMP算法竟然会落选。所以，此次最终投票产出生，KMP算法排到了第二名。 第三名：BFPRT 算法 1973 年，Blum、Floyd、Pratt、Rivest、Tarjan集体出动，合写了一篇题为“Time bou nds for selection” 的论文，给出了一种在数组中选出第k 大元素的算法，俗称"中位数之中位数算法"。依靠一种精心设计的pivot 选取方法，该算法从理论上保证了最坏情形下的线性时间复杂度，打败了平均线性、最坏O(n^2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于骨掌股掌之间，构造出了一个当之无愧的来自圣经的算法。 我在这里简单介绍下在数组中选出第k大元素的时间复杂度为O（N）的算法： 类似快排中的分割算法： 每次分割后都能返回枢纽点在数组中的位置s,然后比较s与k的大小 若大的话，则再次递归划分array[s..n]， 小的话，就递归array[left...s-1] //s为中间枢纽点元素。 否则返回array[s]，就是partition中返回的值。//就是要找到这个s。 找到符合要求的s值后，再遍历输出比s小的那一边的元素。 各位可参考在：算法导论上，第九章中，以期望线性时间做选择，一节中， 我找到了这个寻找数组中第k小的元素的，平均时间复杂度为O（N）的证明：上述程序的期望运行时间，最后证明可得O(n)，且假定元素是不同的。 第四名：Quicksort（快速排序） 快速排序算法几乎涵盖了所有经典算法的所有榜单。它曾获选二十世纪最伟大的十大算法（参考这：细数二十世纪最伟大的10大算法）。关于快速排序算法的具体介绍， 请参考我写的这篇文章：一之续、快速排序算法的深入分析，及十二、快速排序算法之所有版本的c/c++实现。 #1066 : 无间道之并查集 一、问题描述 描述 这天天气晴朗、阳光明媚、鸟语花香，空气中弥漫着春天的气息……额，说远了，总之，小Hi和小Ho决定趁着这朗朗春光出去玩。 但是刚刚离开居住的宾馆不久，抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉，定睛一看还都是地地道道的黑人兄弟！小Hi和小Ho这下就慌了神，捡肥皂事小，这一身百把来斤别一不小心葬身他乡可就没处说去了。 就在两人正举足无措之时，为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸，分别递给了小Hi和小Ho。 小Hi和小Ho接过来，只见上面写道（译为中文）：“本地最大的帮派——青龙帮，诚邀您的加入！”下面还详细的列出了加入青龙帮的种种好处。 于是两人略感心安，在同黑叔叔们交谈一番之后，已是均感相见恨晚。同时，在小Hi和小Ho表示自己不日便将回国之后，黑叔叔们也没有再提加入帮派之事，但是那为首的黑叔叔思索一会，开口道（译为中文）：“我现在有一个难题，思索了很久也没法子解决，既然你们俩都是高材生，不如来帮我看看。” 小Hi和小Ho点了点头表示没问题，于是黑叔叔继续说道：“这个问题是这样的，我们帮派最近混进了许多警察的卧底，但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息，虽然没有办法知道他们具体是哪个阵营的，但是这样的信息也是很重要的，因为我们经常会想要知道某两个人究竟是不是同一阵营的。” 小Hi和小Ho赞同的点了点头，毕竟无间道也都是他们看过的。 黑叔叔接着说道：“于是现在问题就来了，我希望你们能写出这样一个程序，我会有两种操作，一种是告诉它哪两个人是同一阵营的，而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了，不如现在就去我们帮派的总部写好这个程序再走把。” 为了生命安全与……小Hi和小Ho都不得不解决这个问题！那么他们究竟从何下手呢？ 提示：说起来其实就是不断的合并集合嘛~ 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第1行为一个整数N，表示黑叔叔总共进行的操作次数。 《数据结构与算法综合实验》讲义 金英编写 黑龙江大学 计算机科学技术学院 软件学院 2017年 3月 综合实验又称为课程设计，需要学生综合运用所学知识解决与实际应用紧密结合的、规模较大的问题，通过分析、设计、编码和调试等各环节的训练，使学生深刻理解、牢固掌握、综合运用数据结构和算法设计技术，增强分析问题、解决问题的能力，培养项目管理与团队合作精神。 整体要求：（1）系统应具有合理的界面设计，并易于操作，若具有可视化界面更佳；（2）编码风格良好；（3）该系统用控制台程序即可实现；（4）编程语言不限。 本课程要求实验采用基本的软件工程开发方法，将软件开发过程分为需求分析、系统设计、编码实现、系统测试4个阶段。每个阶段设置相应的里程碑进行检查，对学生的设计过程进行评价。 （1）需求分析阶段 首先要充分分析和理解问题，明确要求做什么？限制条件是什么？即要确定需要实现那些功能（任务），并对所需完成的任务做出明确的回答，如，输入数据的类型、值的范围及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式输入，结束标志是什么？是否接受非法输入？对非法输入的回答方式是什么等。另外，还应该为调试程序准备好测试数据，包括合法的输入数据与非法的输入数据。同时，实验小组应该对设计工作进行分工，并形成小组成员通过的书面记录。 （2）概要设计和详细设计阶段 设计通常分为概要设计与详细设计两步。 在进行概要设计时，确定数据的逻辑结构，并要求按照自顶向下逐步求精的原则划分模块，画出模块间的调用关系图。 在进行详细设计时，要求定义数据的存储，并画出各模块（函数）的程序流程图或写出伪代码。 （3）编码实现阶段 在详细设计的基础上，用特定的程序设计语言编写程序。良好的程序设计风格可以保证较快地完成程序测试。程序的每行不要太长，每个函数不要太大，当一个函数太大时，可以考虑将其分解为较小的函数。对函数功能、核心语句、重要的类型和变量等应给出注释。一定要按凹入格式书写程序，分清每条语句的凹入层次，上下对齐层次的括号，以便发现语法错误。 （4）测试阶段 采用测试数据进行测试，列出实际的输入、输出结果、预期结果。 （5）总结与整理报告阶段 调试正确后认真整理源程序及注释，提交带有完整注释且格式良好的源程序，并撰写课程设计报告。 课程设计报告中除了上面提到的分析、设计过程外，还用给出下面几方面的内容。 ①调试分析：调试过程中主要遇到哪些问题？如何解决的？ ②算法分析：核心算法的时间复杂性与空间复杂性分析。 ③改进设想、经验和体会。 并查集--学习详解 文章作者：yx_th000文章来源：Cherish_yimi (https://www.wendangku.net/doc/e65918226.html,/cherish_yimi/) 转 载请注明，谢谢合作。 昨天和今天学习了并查集和trie树，并练习了三道入门题目，理解更为深刻，觉得有必要总结一下，这其中的内容定义之类的是取自网络，操作的说明解释及程序的注释部分为个人理解。 并查集学习： ●并查集：(union-find sets) 一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在 集合的操作，应用很多，如其求无向图的连通分量个数等。最完美的应用当属：实现Kruskar 算法求最小生成树。 ●并查集的精髓（即它的三种操作，结合实现代码模板进行理解）： 1、Make_Set(x) 把每一个元素初始化为一个集合 初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身（也可以根据情况 而变）。 2、Find_Set(x) 查找一个元素所在的集合 查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并 的最终依据。 判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。 合并两个集合，也是使一个集合的祖先成为另一个集合的祖先，具体见示意图 3、Union(x,y) 合并x,y所在的两个集合 合并两个不相交集合操作很简单： 利用Find_Set找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。如图 ●并查集的优化 1、Find_Set(x)时路径压缩 寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find_Se t(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？ 答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它 的子孙节点都直接指向祖先，这样以后再次Find_Set(x)时复杂度就变成O(1)了，如下图所示； 可见，路径压缩方便了以后的查找。 2、Union(x,y)时按秩合并 即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。 主要代码实现 1int father[MAX]; /* father[x]表示x的父节点*/ 2int rank[MAX]; /* rank[x]表示x的秩*/ 3 4 5/* 初始化集合*/ 6void Make_Set(int x) 7{ 8 father[x] = x; //根据实际情况指定的父节点可变化 9 rank[x] = 0; //根据实际情况初始化秩也有所变化 10} 11 12 13/* 查找x元素所在的集合,回溯时压缩路径*/ 14int Find_Set(int x) 15{ 16if (x != father[x]) 17 { 18 father[x] = Find_Set(father[x]); //这个回溯时的压缩路径是精华 poj 1861 Network 题意: Andrew要在公司里用电缆连接n个集线器，要用总长度最小的线连接，求出其中最长的那根电缆。 也就是告诉n个顶点，m条边，求最小生成树的最大边。并把生成树的每条边输出来，Sample 里面的输出有问题，应该是三条。 给出节点个数m和边数n，下面n行给出边(x,y)以及权值w。输出第一行为最小生成树中的最大边权值，第二行为一个可行生成树方案的边数k，下面k行为可行生成树的k条边。题目是Special Judge，意思就是不具有唯一解，可能有多解，样例输出为以下结果也可算对。1 3 1 3 2 4 2 3 一样按照Kruskal解题即可，结果虽然不唯一，但是最小生成树一定是可行解之一。将边加入生成树时记录最大权值和边信息然后输出即可。 #include /* 初始化集合 */ void Make_Set(int x) { father[x] = x; rank[x] = 0; } /* 查找x元素所在的集合,回溯时压缩路径 */ int Find_Set(int x) { if (x != father[x]) { father[x] = Find_Set(father[x]); } return father[x]; } /* 合并x,y所在的集合 */ void Union(int x, int y) { if (x == y) return; if (rank[x] > rank[y]) { father[y] = x; } else { if (rank[x] == rank[y]) { rank[y]++; } father[x] = y; } } int main() { int i, j, m, n, k, max; int x, y; scanf("%d%d", &m, &n); /* 读入边数据 */ACM一期 基础训练计划
信息学奥赛-并查集
数据结构
并查集检查网络课程设计报告
数据结构复习要点
并查集超级易懂讲解
数据结构总结
并查集2
北京师范大学《数据结构》课程教学大纲
并查集及例题题解
poj2513_欧拉通路+并查集+hashtrie 收藏
28个不得不看的经典编程算法!!数学软件计算机的进来!~
1066#无间道之并查集
《数据结构与算法综合实验》讲义----2017版[PDF版]
并查集
acm并查集基础题目