浅谈带权并查集

算法背景

我们知道并查集,即 Disjoint-set data structure

是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示,其实也就是维护一颗森林, 操作的时间复杂度是一个接近常数的函数,,

并查集的合并和查询操作都很容易理解, 现在来复习一下并查集在集合关系方面的一些作用

算法思想

其实很久以前都学了这个了 一直没有碰到维护集合问题的题目,又给忘记了,这次又碰到了就来复习一下QAQ

以POJ1182食物链这道题为例,这个题目是维护三个集合的关系的,,,

“1 X Y”,表示X和Y是同类。
“2 X Y”,表示X吃Y。

1) 当前的话与前面的某些真的话冲突,就是假话;

2) 当前的话中X或Y比N大,就是假话;

3) 当前的话表示X吃X,就是假话。

看到这个题目 我们知道物种之间只有吃与被吃的关系,那么这个关系其实就是一个如下图的环

《浅谈带权并查集》

那么我们现在把环状化为链状 即为 A -> B – > C – > A -> B -> C -> ……

这样每条链的关系就是一定的, 即定义一个节点到根节点的数组dis[i] mod 3 的距离判定关系

我们要寻找假话的次数,首先我们可以明确,两个节点一定是在一个集合(链)内才可以判断真假(不同的话怎么说也可以是真的啊),不同集合之间是无法相互影响的,

在同一个集合的,那么他们的关系,在mod3之后必定是一个定值(0,1,2)(一个食物链内的相对距离一定) 判断一下就好了

实现的算法的话 AC代码的注释已经带了,(虽然是很久以前写的吧

#include <bits/stdc++.h>
using namespace std;

#define N 50005

int pre[N], relation[N];

void init(int n)
{
    for(int i = 0;i <= n; i++) {
        pre[i] = i;
        relation[i] = 0;
    }
}
/*更新的同步,先将当前根节点与其根节点相连,然后更新其与根节点的关系
当前节点x与其根节点r的更新方法为:
    (x与其父节点的关系+父节点与根节点的关系)%3
    更新x节点的数据之前需要更新其父节点的数据
    更新的顺序为 :从根节点向下直到更新到当前节点x的父节点 
*/
int find(int x)
{
    if(pre[x] == x) {    //x直接就是根节点 
        return x;
    }
    else {
        int temp = pre[x];  //将当前节点的父节点更新为根节点
        pre[x] = find(temp); //更新当前节点与根节点的关系,由X→X父节点,X父节点→根节点 
        //更新为X→X父根节点, 所以在此之前必须更新X父节点与根节点的关系
        relation[x] = (relation[x]+ relation[temp]) % 3; 
        return pre[x];
    } 
}
int main()
{
    int n, m, x, y, fx, fy, d, ans;
    scanf("%d%d",&n,&m);
        ans = 0;
        init(n);
        for(int i = 0;i < m; i++) {
            scanf("%d%d%d",&d,&x,&y);
            if(x>n || y>n) {
                ans++;
                continue;
            }
            if(d==2 && x==y) {
                ans++;
                continue;
            }
            fx = find(x);
            fy = find(y);
            if(fx == fy) {  // 属于同一个子集 
                //如果x,y同类那么它们对应的根节点应该一样
                if(d==1 && relation[x]!=relation[y]) {
                    ans++;
                }
                //如果不是同类,加入X与Y的关系后,X相对与根节点的关系(X根→Y,Y→X(即3-(d-1)=2)即X根→X)应该是不变的 
                // d = 2表示x-y=1,而y→x=3- (x→y)=2 
                 if(d==2 && relation[x]!=(relation[y]+2)%3) {
                    ans++;
                 } 
            }
            else {   //合并两个联通区域
                pre[fy] = fx; // y父的根节点更新为x的根
                //(d-1)为X与Y的关系,3-relation[y] 是y与y的根节点关系,relation[x]是其根节点与X的关系
                //X根 →X,X →Y根,即X根→Y根 
                relation[fy] = (relation[x]+(d-1)+(3-relation[y])) % 3;
            }
        }
        printf("%d\n",ans);
return 0;
}

算法应用

下面是几道关于这个算法具体实现的例题QAQ

CF396D 只有两个关系,很简单的判定 不过要加上map维护一下QAQ

https://blog.csdn.net/wang2332/article/details/78108485

——-未完待续———-

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注