湖北建设厅网站查询,海口网站建设加q.479185700,凡科网做网站如何推广,宜昌网站推广优化技巧最近几日理了理学过的很多oi知识。。。发现不知不觉就有很多的知识忘记了。。。 在聊聊并查集的时候顺便当作巩固吧。。。。 什么是并查集呢? ( Union Find Set ) 是一种用于处理分离集合的抽象数据结构类型。 具体一点: 当我们给出两个元素的一个无序对#xff08;a,b#… 最近几日理了理学过的很多oi知识。。。发现不知不觉就有很多的知识忘记了。。。 在聊聊并查集的时候顺便当作巩固吧。。。。 什么是并查集呢? ( Union Find Set ) 是一种用于处理分离集合的抽象数据结构类型。 具体一点: 当我们给出两个元素的一个无序对a,b时需要快速合并a和b所在的集合这期间需要反复查找出某元素所在的集合“并”、“查”和“集”三字由此而来。也就是说并查集的作用是动态地维护和处理集合元素之间的复杂关系。 在并查集中n个不同的元素被分为若干组每组是一个集合这种集合就叫做“分离集合”。并查集支持查找一个元素所属的集合以及两个元素各自所属集合的合并操作。 例如我们有这样一个问题 一个城镇里居住着n个市民已知一些人互为朋友而且朋友的朋友也是朋友也就是说如果A和B是朋友C和B是朋友则A和C也是朋友请你根据给出的若干组朋友关系求出最大的一个朋友圈的人数。 这就有了并查集的用武之地了一开始我们把所有人都各自放在一个集合中然后根据依次给出的朋友关系查找判断两个人是否属于同一个集合是否已经是朋友如果不在同一个集合则将这两个集合合并成一个集合行成一个朋友圈最后看哪个集合的元素最多并输出个数即可。 然而并查集有什么主要操作呢 使用并查集首先要记录一组分离的动态集合S {S1S2···Sn}每个集合还要设置一个代表来识别代表只是要选择该集合中的某个元素即可哪一个元素被选作代表是无所谓的重要的是如果请求某一动态集合的代表两次且在两次请求间不修改集合则两次得到的答案应该是相同的。并查集主要有三种操作初始化、查找与合并。 1初始化make-set(x) 建立一个新的集合其仅有的成员是x同时就是代表。由于各集合是分离的所以要求x在没有其他集合中出现过。使用并查集前都需要执行一次初始化操作无论采用何种实现方式其时间复杂度都是On。 2查找find-set(x) 查找一个元素所在的集合本操作返回一个包含x的集合的代表。查找是并查集的核心操作也是优化并查集效率的重点。 3合并merge(xy) 将包含x和y的动态集合假设为Sx和Sy合并成一个新的集合S本操作返回集合Sx∪Sy的代表。一般来说在不同的实现中通常以Sx或者Sy的代表作为新集合的代表。合并之前一般要先判断两个元素是否属于同一集合这可以通过查找操作来实现。 终于到了并查集的实现了 并查集可以采用数组、链表和树三种数据结构来实现选择不同的实现方式会给查找操作和合并操作的效率带来很大的差别。 并查集的数组实现 实现并查集的最简单的方法就是用数组记录每个元素所属集合的编号A[i] j 表示元素i属于第j 类集合初始化A[i] i。查找元素所属的集合时只需读出数组中记录的该元素所属集合的编号A[i]时间复杂度为O1。合并两个元素各自所属集合时需要将数组中属于其中一个集合的元素所对应的数组元素值全部更新为另一个集合的编号值时间复杂度为On。所以用数组实现并查集是最简单的方法而且容易理解实际使用较多。但是合并操作的代价太高在最坏的情况下所有集合合并成一个集合的总代价会达到On2。 并查集的链表实现 用链表实现并查集也是一种很常见的手段。每个分离集合对应一个链表链表有一个表头每个元素有一个指针指向表头表明了它所属集合的类别另设一个指针指向它的下一个元素同时为了方便实现再设一个指针last表示链表的表尾。 因为并查集问题处理的对象往往都是连续的整数所以一般选择用静态数组来模拟链表用下标对应集合的元素。具体数据结构体定义如下qwq struct node{int head,next,last;
}S[maxn];此时初始化和查找操作的实现就很简单了。 make-set(x){S[x].head x;S[x].next 0;
}
find-set(x){return S[x].head
}对于合并操作我们先假设mergexy的参数是有序的是把y所属的集合合并到x所在的集合。首先执行查找操作当出现find-setx≠ find-sety时直接将y的表头接到x的表尾同时将y所在集合的所有元素head值设为find-setxx的表尾也设为y的表尾。需要注意的是last指针只要在表头结点中记录即可因为每一次查找到find-setx都可以得到表头元素而链表中其他元素记录last值是毫无意义的。 考虑到输入数据的特殊性根据以上合并方法我们总是把y接到x后面如果y所在的集合非常大每次复制的代价就会非常高比如输入数据形如2,13,14,1·····n1显然y所在的集合就会越来越庞大此时时间复杂度就会达到On2。不过我们可以很快滴想到一个优化方法不妨比较x和y所在集合的大小把较短的链表接在较长的链表尾部这样效果是一样的但时间效率肯定不比原来差。具体实现时可以在node里多设一个number域用来记录此条链表中成员的个数。显然number记录在表头元素中即可。将两个链表合并的时候只需要将链表的number域相加因此维护起来是非常方便的。这种快速实现的方法称为“加权启发式”合并这里的权就是指number域。假设有n个元素则可以证明这种方法合并操作的总次数不超过nlog2n次。 merge(x,y){x find-set(x);y find-set(y);if(x.number y.number)merge(x,y);merge(y,x);
}以上是并查集的两种实现方法qwq。然而最最最重要以及实用的是并查集的树实现。我会在 谈一谈并查集QAQ下 中仔细讲解qwq。 转载于:https://www.cnblogs.com/excellent-zzy/p/10686911.html
