精华内容
下载资源
问答
  • 种类并查集

    2021-03-29 14:49:56
    种类并查集 在一般的并查集当中,普通并查集只能维护一般的等价类关系,如果存在多个等价类关系,就需要用到种类并查集了。 原理 集合中的元素直间存在两种关系,假设AAA与BBB的关系是关系1,BBB与CCC的关系是关系...

    种类并查集

    在一般的并查集当中,普通并查集只能维护一般的等价类关系,如果存在多个等价类关系,就需要用到种类并查集了。

    原理

    集合中的元素直间存在两种关系,假设AABB的关系是关系1,BBCC的关系是关系22,那么AACC一定存在关系,这种情况才能用种类并查集(即关系传递)。

    例如:朋友与敌人关系,朋友的朋友是朋友,朋友的敌人是敌人,敌人的朋友是敌人,敌人的敌人是朋友。这种相互传递的关系才能用种类并查集,如果是单链的关系,是不能用种类并查集维护的。

    我们创建三倍空间的大小的并查集,其中另外两个元素空间是原集合的拷贝。例如AAAA'AA''

    AA'相等价的是A的朋友,和AA''相等价的是A的敌人。比如A和B是朋友,那么就让AA'BB相连,BB'AA相连。同时B的敌人仍是A的敌人,A的敌人也是B的敌人,所以AA''BB''相连。构成的这样一种关系。同时我们还发现,第一个并查集空间并不表示任何空间,我们将这个并查集和AA'合并,省去一个并查集空间。

    切记,验证这个题是否符合种类并查集,要验证每一步合并都是合法合理的,例如,上述中,AA''BB''这两个合并,满足A的敌人和B的敌人相同,如果题目要求A的敌人是B的敌人,但是B的敌人不是A的敌人,那么这样连接并查集中的元素就是不合法的。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,239
精华内容 495
关键字:

种类并查集